dijkstra算法求解最短路徑

#include<iostream>
using namespace std;
#define MaxInt 999 //極大值
#define MVNum 100  //最大頂點數
typedef char VertexType;
struct Graph{
	VertexType vexs[MVNum];//頂點表
	int arc[MVNum][MVNum];//鄰接矩陣
	int vexnum;//頂點數
};


void Dijkstra_sort(Graph G,int v0)
{
	int n=G.vexnum;
	int Path[n];//記錄前驅
	int D[n]; //記錄相對最短路徑
	bool S[n];//判斷目前路徑長度是否為最短路徑

	for(int i=0;i<n;i++)
	{
		S[i]=false;
		D[i]=G.arc[v0][i];
		if(D[i]<MaxInt)
		Path[i]=v0;
		else 
		Path[i]=-1;
	}
	S[v0]=true;
	D[v0]=0;
	//初始化
	int v;
	for(int i=0;i<n-1;i++)
	{
		int min=MaxInt;
		for(int w=0;w<n;w++)
		{

			if(D[w]<min&&!S[w])
			{
				min=D[w];
				v=w;
			}
			
		}
		S[v]=true;
		for(int w=0;w<n;w++)
		{
			if(!S[w]&&D[w]>(D[v]+G.arc[v][w]))
			{
				D[w]=D[v]+G.arc[v][w];
				Path[w]=v;
			}
		}
	}
	for(int i=0;i<G.vexnum;i++)
	{
		if(i!=v0)
		{
			cout<<v0<<"到"<<i<<"的最短路徑="<<D[i]<<endl;
			cout<<"路線為: " ;
			for(int k=i;k!=v0;k=Path[k])
			{	
				cout<<k<<"<---";
			}
			cout<<v0<<endl;
		}
		
	}        
}

void GradeMap(Graph &G)//建立圖1
{
	G.vexnum=5;
	for(int i=0;i<=G.vexnum;i++)
	{
		for(int j=0;j<=G.vexnum;j++)
		{
			G.arc[i][j]=MaxInt;
		}
	}
	G.arc[0][4]=10;
	G.arc[0][2]=30;
	G.arc[0][1]=100;
	G.arc[2][1]=60;
	G.arc[2][3]=60;
	G.arc[3][1]=10;
	G.arc[4][3]=50;
	
	//輸出一下
	for(int p=0;p<G.vexnum;p++)
	{
		for(int q=0;q<G.vexnum;q++)
		{
			cout<<G.arc[p][q]<<"\t";
		}
		cout<<endl;
	}
}

int main()
{
	Graph G;
	GradeMap(G);
	Dijkstra_sort(G,0);下标為0的點到其他點的距離
	return 0;
}