单源最短路径-Dijkstra（迪杰斯特拉算法）

迪杰斯特拉算法时间复杂度为O(n^2)，其中n为顶点个数。

该算法用于求单源最短路径。并且图中的边不允许带负权值。

#include <iostream>
using namespace std;

#define Maxsize 100
typedef char VertexType;
typedef int EdgeType;

typedef struct{
	VertexType Vex[Maxsize];
	EdgeType edge[Maxsize][Maxsize];
	int vexnum,arcnum;
}MGraph;

void Dijkstra(MGraph G,int v,int dist[],int path[]){
	int set[Maxsize];
	int min,i,j,u;
	for(i=0;i<G.vexnum;i++){	//初始化 
		dist[i]=G.edge[v][i];
		set[i]=0;
		if(G.edge[v][i]<INF)	//两顶点无边
			path[i]=v;
		else
			path[i]=-1; 
	}
	set[v]=1;
	path[v]=-1;
	for(i=1;i<=G.vexnum;i++){
		min=INF;
		for(j=0;j<G.vexnum;j++){
			if(set[j]==0&&dist[j]<min){	//未加入源S且距离小于min 
				u=j;
				min=dist[j];	
			}
			set[u]=1;	//将选出的顶点并入最短路径中
			for(j=0;j<G.vexnum;j++){	//更新源S与剩余顶点距离 
				if(set[j]==0&&dist[u]+G.edge[u][j]<dist[j]){
					dist[j]=dist[u]+G.edge[u][j];
					path[j]=u;
				}
			} 
		}
	}
}