c++实现最短路径迪杰斯特拉算法

#include 
using namespace std;
#define MAXVEX 9 //最大顶点数
#define INFINITY 65535 //极大值  即无穷

typedef struct
{
	string vexs[MAXVEX]; //顶点表
	int arc[MAXVEX][MAXVEX]; //邻接矩阵，可看做边表
	int numNodes, numEdges; // 图中当前的顶点数和边数
}MGraph;

void CreateMGraph(MGraph& G)
{
	int i, j, k, w;
	cout << "请输入顶点数和边数" << endl;
	cin >> G.numNodes >> G.numEdges;
	for (i = 0; i < G.numNodes; i++) //建立顶点表
	{
		cout << "请输入顶点值" << endl;
		cin >> G.vexs[i];
	}
	for (i = 0; i < G.numNodes; i++)
	{
		for (j = 0; j < G.numNodes; j++)
		{
			G.arc[i][j] = INFINITY;  //邻接矩阵初始化
		}
	}
	for (k = 0; k < G.numEdges; k++)  //建立邻接矩阵
	{
		cout << "请输入边（vi，vj）上的下标i，下标j和权" << endl;  //输入边上的权
		cin >> i >> j >> w;
		G.arc[i][j] = w;
		G.arc[j][i] = G.arc[i][j];  //无向图中矩阵对称
	}
}

typedef int Patharc[MAXVEX];  //用于存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX];  //用于存储到各点最短路径的权值和

void ShortestPath_Dijkstra(MGraph G, int v0, Patharc& P, ShortPathTable& D)
{
	int k = 0, min;
	int final[MAXVEX];  //final[w] = 1表示求得顶点v0至vw的最短路径
	for (int v = 0; v < G.numNodes; v++)  //初始化数据
	{
		final[v] = 0;  //全部顶点初始化为未知最短路径状态
		D[v] = G.arc[v0][v];  //将与v0点有连线的顶点加上权值
		P[v] = -1;  //初始化路径数组P为-1
	}
	D[v0] = 0;  //v0至v0路径为0
	final[v0] = 1;  //v0至v0不需要求路径
	for (int v = 1; v < G.numNodes; v++)  //开始主循环，每次求得v0到某个顶点v的最短路径
	{
		min = INFINITY;
		for (int w = 0; w < G.numNodes; w++)  //寻找距离v0最近的顶点
		{
			if (!final[w] && D[w] < min)
			{
				min = D[w];
				k = w;
			}
		}
		final[k] = 1;  //将目前找到的最近的顶点置为1
		for (int w = 0; w < G.numNodes; w++)  //修正当前最短路径及距离
		{
			if (!final[w] && (min + G.arc[k][w] < D[w]))  //如果经过v顶点的路径比现在这条路径的长度短的话
			{
				D[w] = min + G.arc[k][w];  //修改当前的路径长度
				P[w] = k;
			}
		}
	}
	for (int i = 0; i < G.numNodes; i++)
	{
		cout << P[i] << " ";
	}
	cout << endl;
	for (int i = 0; i < G.numNodes; i++)
	{
		cout << D[i] << " ";
	}
	cout << endl;
}

int main()
{
	MGraph G;
	CreateMGraph(G);
	Patharc P;
	ShortPathTable D;
	ShortestPath_Dijkstra(G, 0, P, D);
}