dijkstra.cpp

经典求最短路径算法程序--dijkstra算法。完整的C++源码程序。

#include <iostream.h>


#define maxint 999999

void Dijkstra(int n,int v,int dist[],int prev[],int **table)
{  
    //其中n指n个节点,v指起点,dist[i]记录源点到i点的最短特殊路径,prev[i]记录在特殊路径当中i点的前一个点,table[][]就是无向图的邻接矩阵
    int i,j;
    bool s[maxint];   //maxint是个非常大的数
	int count=1;

    for (i=1;i<=n;++i)
    {
        dist[i] = table[v][i];
        s[i] = false;
        if (dist[i] == maxint) prev[i] = 0;   //将该点的前一个点赋为0,应为它不与v点直接相连
        else     prev[i] = v;   
     }
     dist[v] = 0; s[v] = true;      //与prim不同的是初始时从源点出发 
	 cout<<"\n到各个点的最短路径依次为:"<<endl;
     for (i=1;i<n;++i)
     {
         int temp = maxint;
         int u = v;
         for (j=1;j<=n;++j)
         {
              if ((!s[j])&&(dist[j]<temp))           //先找和V点距离最短并且没有被访问过的点u 
              {
                    u = j;                           
                    temp = dist[j];
               }
         }
         s[u] = true;                              //找到之后访问
		
         for (j=1;j<=n;++j)
         {
              if ((!s[j])&&table[u][j]<maxint)             //再找与u点相邻的点
              {
                 int newdist = dist[u] + table[u][j];     
                 if (newdist<dist[j])
                 {
                      dist[j] = newdist;           //如果存在点与u点的距离加上u点到原点的距离比原dist[j]要小，那么newidist为从源点到该点的最短特殊路径
                      prev[j] = u;       //将j的前驱记为u
                  }
              }
          }
      }
	 for(j=1;j<=n;j++)
	 {
		 int num;
		 num=j;
		 count=1;
		 if(j==v)
		 {
			 cout<<"到点"<<j<<"不需要跳跃..."<<endl;
			 continue;
		 }
		 else
		 {
			 if(prev[j]==v)
			 {
				 cout<<"到点"<<j<<"的最短路径需要跳跃1次."<<endl;
				 continue;
			 }
			 else
			 {
				while(prev[num]!=v)
				{
					count++;
					num=prev[num];
				}
				cout<<"到点"<<j<<"的最短路径需要跳跃"<<count<<"次."<<endl;
			 }
		 }
	 }
			 
}

int main()
{
	int *dist,*prev,**table;
	int n,v;
	int ver1=0,ver2=0;
	int w;


	cout<<"      -------------------------最短路径问题---------------------"<<endl;
	cout<<endl;
	cout<<"      程序功能：运用Dijkstra算法找出无向图中从源点到各个点的最短路径需要跳跃的次数。"<<endl;
	cout<<"      输入:无向图的相关信息。"<<endl;
	cout<<"      输出:从源点到各个点的最短路径需要跳跃多少次。"<<endl;
	cout<<endl;

	cout<<"请输入图的顶点个数:";
	cin>>n;

	
	dist=new int[n+1];
	prev=new int[n+1];
	table=new int*[n+1];
	for(int i=0;i<n+1;i++)
		table[i]=new int[n+1];

	for(i=0;i<n+1;i++)
	{
		for(int j=0;j<n+1;j++)
			table[i][j]=maxint;
	}

	for(i=0;i<n+1;i++)
		table[i][i]=0;


	cout<<"请输入各个相邻接的两个顶点及其权值(以0 0 0结束输入):"<<endl;
	do
	{
		cin>>ver1>>ver2>>w;
		if(ver1!=0||ver2!=0)
		{
			table[ver1][ver2]=w;
			table[ver2][ver1]=w;
		}
	}while(ver1!=0||ver2!=0);
	
	cout<<"请输入源点:";
	cin>>v;


	Dijkstra(n,v,dist,prev,table);

	return 0;
}