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

#include 
#include 
#include 
using namespace std;

#define INFINITY 65535//無邊時的權值
#define MAX_VERTEX_NUM 10//最大頂點數(shù)

typedef struct MGraph{
	string vexs[10];//頂點信息
	int arcs[10][10];//鄰接矩陣
	int vexnum, arcnum;//頂點數(shù)和邊數(shù)
}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<