单源最短路径问题.cpp

贪心算法解一系列算法经典问题

// 单源最短路径Dijkstra算法

#include <stdio.h>
#define VertexNum 5	//顶点数
#define EdgeNum 7	//边数
#define X 10000		//最大权值

// 邻接矩阵初值(权值)
int Graph[VertexNum][VertexNum]=
{	//1   2   3   4   5
	  X, 10,  X, 30,100, //1
	  X,  X, 50,  X,  X, //2
	  X,  X,  X,  X, 10, //3
	  X,  X, 20,  X, 60, //4
	  X,  X,  X,  X,  X, //5
};

int Visited[VertexNum];		//访问标识(0或1)
int path[VertexNum];		//最短路径序列
int Distance[VertexNum];	//最短路径值

// Dijkstra算法，Begin为源点
void Dijkstra(int Begin)
{
	//输出原始数据
	int MinEdge,i,j,Vertex;
	printf("          1   2   3   4   5\n");
	printf("----------------------------\n");
	printf("s:%d (V)",Begin);
	for(i=0; i<VertexNum; i++)
		if (Distance[i]==X) printf("  ∞");
		else printf("%4d",Distance[i]);
	printf("\n");

	//寻找n-1条最小路径
	for(j=1; j<VertexNum; j++)
	{
		//寻找当前最小路径值
		MinEdge=X;
		Vertex=0;
		for(i=0; i<VertexNum; i++)
			if (Visited[i]==0 && Distance[i]<MinEdge)
			{
				Vertex=i;
				MinEdge=Distance[i];
			}
		Visited[Vertex]=1;	//Vertex顶点已访问

		//重新计算当前最短路径
		printf("s:%d (%d)",j,Vertex+1);
		for(i=0; i<VertexNum; i++)
		{
			int sum=Distance[Vertex]+Graph[Vertex][i];
			if (Visited[i]==0 && sum<Distance[i])
			{
				Distance[i]=sum;
				path[i]=Vertex;
			}
			if (Distance[i]==X) printf("  ∞");
			else printf("%4d",Distance[i]);
		}
		printf("\n");
//for(i=0; i<VertexNum; i++) printf("%4d",path[i]+1);
//printf("\n");
	}
}

void main()
{
	int i,j,k=0;
	//设置初值
	for(i=0; i<VertexNum; i++) 
	{
		Visited[i]=0;
		path[i]=k;
		Distance[i]=Graph[k][i];
	}
	Visited[k]=1;	//源点已访问

	Dijkstra(k);	//顶点1为源点

	//输出所有最短路径
	printf("\nAll Path:\n");
	for(i=1; i<VertexNum; i++)
	{
		j=i;
		printf("Path%d: [%d]  ",i,Distance[i]);
		do
		{
			printf("%d<--",j+1);
			j=path[j];
		} while(j!=0);
		printf("1\n");
	}
	printf("\n");
}