迪杰斯特拉算法（可打印最短路径）

#include 
#include 
#include 
using namespace std;

#define INFINITY 65535//无边时的权值
#define MAX_VERTEX_NUM 10//最大顶点数

typedef struct MGraph{
	string vexs[10];//顶点信息
	int arcs[10][10];//邻接矩阵
	int vexnum, arcnum;//顶点数和边数
}MGraph;

int LocateVex(MGraph G, string u)//返回顶点u在图中的位置
{
	for(int i=0; i>G.vexnum>>G.arcnum;

	cout<<"请输入顶点：";
	for(i=0; i>G.vexs[i];

	for(i=0; i>v1>>v2>>w;
		i=LocateVex(G, v1);
		j=LocateVex(G, v2);
		G.arcs[i][j]=w;
	}
}

//迪杰斯特拉算法求有向网G的v0顶点到其余顶点v的最短路径p[v]及带权长度D[v]
//p[][]=-1表示没有路径，p[v][i]存的是从v0到v当前求得的最短路径经过的第i+1个顶点(这是打印最短路径的关键)，则v0到v的最短路径即为p[v][0]到p[v][j]直到p[v][j]=-1,路径打印完毕。
//final[v]为true当且仅当v∈S,即已经求得从v0到v的最短路径。
void ShortestPath_DIJ(MGraph G, int v0, int p[][MAX_VERTEX_NUM], int D[])
{
	int v, w, i, j, min;
	bool final[10];
	
	for(v=0; vv->w的距离<目前v0->w的距离
					D[w]=min+G.arcs[v][w];//更新D[w]
					for(j=0; j-1)
					cout<