shortroad.cpp

完整实现了单源最短路径的算法。 采用的是贪心算法思想。

//作者：周亮 Jackson
#include <iostream.h>
#include <cstdio>
const int maxint = 1000000;
bool s[maxint];   // maxint是个非常大的数

void Dijkstra(int n,int v,int dist[],int prev[],int * * c){  
    // 其中n指n个节点,v指起点,dist[i]记录源点到i点的最短特殊路径,
	// prev[i]记录在特殊路径当中i点的前一个点,c[][]就是有向图的邻接矩阵
    int i,j;
	
    for (i=1;i<=n;i++)
    {
        dist[i] = c[v][i];
        s[i] = false;
        if (dist[i] == maxint) prev[i] = 0;   // 将该点的前一个点赋为0,因为它不与v点直接相连
        else     prev[i] = v;   
	}
	dist[v] = 0; s[v] = true;      // 初始时从源点出发
	for (i=1;i<n;i++)
	{
		int temp = maxint;
		int u = v;
		for (j=1;j<=n;j++)
		{
			if ((!s[j]) && (dist[j]<temp))
			{
				u = j;
				temp = dist[j];
			}
		}
		s[u] = true;
		for (j=1;j<=n;j++)
		{
			if ((!s[j]) && c[u][j]<maxint)
			{
				int newdist = dist[u] + c[u][j];     //newidist为从源点到该点的最短特殊路径
				if (newdist<dist[j])
				{
					dist[j] = newdist;
					prev[j] = u;
				}
			}
		}
	}
}

void main()
{
	int **c;
	int t;
	int dist[6];
	int prev[6];
	
	c = new int *[6] ;              //申请矩阵空间
	for(int r=1 ; r<6 ; r++)
		c[r] = new int [6] ;
	
	for(int i=1; i<=5; i++)        //给无向图赋值
		for(int j=1; j<=5; j++)
		{
			if(i==j) c[i][j]=0;
			else c[i][j] = maxint;  	 
		}
		c[1][2]=10;
		c[1][4]=30;
		c[1][5]=100;
		c[2][3]=50;
		c[3][5]=10;
		c[4][5]=60;
		c[4][3]=20;
		
		Dijkstra(5,1,dist,prev,c);
		
		for(int k=2; k<=5; k++)
		{
			cout<<"从顶点1到顶点"<<k<<"的最短路径长度为："<<dist[k]<<endl;
			cout<<"路径标志为："<< k ;
			for(t=k;t>=2;t=prev[t]){
				cout<<" <- " <<prev[t];
			}
			cout<<endl<<endl;
		}
		
		/*
		cout<<"从顶点1到顶点3的最短路径长度为："<<dist[3]<<endl;
		cout<<"路径标志为："<<" 3 ";
		for(t=3;t>=2;t=prev[t]){
		cout<<" <- " <<prev[t];
		}
		cout<<endl<<endl;
		
		  cout<<"从顶点1到顶点4的最短路径长度为："<<dist[4]<<endl;
		  cout<<"路径标志为："<<" 4 ";
		  for(t=4;t>=2;t=prev[t]){
		  cout<<" <- " <<prev[t];
		  }
		  cout<<endl<<endl;
		  
			cout<<"从顶点1到顶点5的最短路径长度为："<<dist[5]<<endl;
			cout<<"路径标志为："<<" 5 ";
			for(t=5;t>=2;t=prev[t]){
			cout<<" <- " <<prev[t];
			}
			cout<<endl<<endl;
		*/
}