[C++知识库]Dijkstra算法，最短路径，c/c++描述

??首先感谢bilibili懒猫老师的精彩讲解。让学生茅塞顿开，入门了。
??求图里两顶点间的最短路径，对于不带权图，就是两顶点间的包含最少边数的路径；对于带权图，就是路径中边的权值和最小的那条路径。
??关于最短路径，在老鼠走迷宫里，我们遇到过，用队列记录走过的路径，依据广度优先的原则，第一个到达终点的路径就是最短路径。
??对于图里两顶点间的路径，我们也可以先求出图里连接这俩顶点的所有路径，并找出来权值最小的那一条。
??Dijstra算法课本定义是：把图里顶点分成包括起点在内的已求出最短路径的点，和未求出最短路径的顶点，依托这两个点集，按最短路径权值增加的顺序求出所有最短路径。
??Dijstra算法依据是这样的：图里所有最短路径都是在其他最短路径的基础上延伸而来的。最短路径上起点到路径中每一个点的路径都是最短路径。这个可以由归纳法证明。
??例如对于包含A在内的n个点，已求出了n-2条最短路径，除了A到B。那么A到B的最短路径都是在A到其他点的最短路径上延伸到B而来的，其中的最小值就是A到B的最短路径。假如A到B，有边，且权值最小，结论最短路径上起点到每个点的路径都是最短路径仍然成立。
??再具体讲Dijkstra算法：已求得一些点的最短路径，不包括B。求起点A—>B的最短路径，正确思路是什么呢？依然是从A到B的所有路径中找出最短的那一条。有直接A到B的路径，还有途经已经求得最短路径的那些点，如C，再连接到B，这些路径中求得最短的路径，作为A到B的“最短路径”，因为我们并没有遍历A到B的所有路径，所有这个“最短路径”是可能不准确的。对所有未得到最短路径的点，都以此算法计算出其“最短路径”，其中权值最短的那一条，就是实实在在准确的最短路径。可能不是点B，但总的来说，又多求了一个点，直至求完所有的点。
??本例题的结果也可以佐证。
??几个关键点的处理：
??如何区分已求得和未求得最短路径的点：设置一个bool数组check[]，凡是求得最短路径的点，其值为true。待求最短路径的点，其值为false。
??如何记录最终的最短路径：我们需要保存两个方面的数据，路径长度和路径里经过的点的下标。我们设置一个结构体变量，来保存这些值：

struct ShortestPath {
	int pathLength ;
	int indexOfVertexInPath[MAXVERTEX];
	int numVertex;
}

??如何计算最短路径：算法见上面文字分析，这是设计程序的理论依据。
??还有就是，在计算路径长度时，路径里的点的信息，也要及时更新，与路径保持同步。
??本程序的时间复杂度O（n^3）。
??函数createGraphAdjMatrix：建立图的邻接矩阵。
??函数dispalyGraphAdjMatrix显示图的邻接矩阵，以检验图的建立是否正确。
??函数DijkstraSolutionShortestPath，求出从起点开始的所有最短路径。
??函数和变量命名尽量见名知意，很好理解。比用 i，j，k 强。
??所有代码如下，先是包含main函数的源文件：

#include<iostream>
#include<stdio.h>
using namespace std;
#define MAXVERTEX 15
#define INFINI 6000

struct GraphAdjaMatrix {
	char vertexes[MAXVERTEX];
	int edges[MAXVERTEX][MAXVERTEX];
	int numVertexes;
	int numEdges;
};

struct ShortestPath {
	int pathLength ;
	int indexOfVertexInPath[MAXVERTEX];
	int numVertex;
};

extern void createGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix,
			int numVertexes,int numEdges,int edges[][7],char vertexes[]);
extern void dispalyGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix);
extern void DijkstraSolutionShortestPath(GraphAdjaMatrix& graphAdjMatrix,
						ShortestPath allShortestPath[7],int indexStart);

int main() {
	GraphAdjaMatrix graphAdjMatrix ;
	int numVertexes = 7, numEdges = 12;
	int edges[][7] = {	{0,4,6,6,INFINI,INFINI,INFINI},
						{INFINI,0,1,INFINI,7,INFINI,INFINI},
						{INFINI,INFINI,0,INFINI,6,4,INFINI},
						{INFINI,INFINI,2,0,INFINI,5,INFINI},
						{INFINI,INFINI,INFINI,INFINI,0,INFINI,6},
						{INFINI,INFINI,INFINI,INFINI,1,0,8},
						{INFINI,INFINI,INFINI,INFINI,INFINI,INFINI,0} };
	char vertexes[] = {'0','1','2','3','4','5','6'};

	createGraphAdjMatrix(graphAdjMatrix,numVertexes,numEdges,edges,vertexes);

	dispalyGraphAdjMatrix(graphAdjMatrix);
	cout << endl;

	ShortestPath allShortestPath[7];
	int indexStart = 0;
	DijkstraSolutionShortestPath(graphAdjMatrix,allShortestPath,indexStart);

	cout << "shortest path : " << endl;
	for(int i = 0 ; i < graphAdjMatrix.numVertexes ; i++)
		if (i != indexStart) {
			cout<< graphAdjMatrix.vertexes[indexStart] << " to " << graphAdjMatrix.vertexes[i] << " , ";
			cout << " path length : ";
			printf("%-2d ,     path : ",allShortestPath[i].pathLength);
			
			for (int j = 0; j < allShortestPath[i].numVertex; j++)
				cout << graphAdjMatrix.vertexes[allShortestPath[i].indexOfVertexInPath[j]] << " ";
			
			cout << endl;
		}

	return 0;
}

然后是各函数所在源文件：

#include<iostream>
#include<stdio.h>
using namespace std;
#define MAXVERTEX 15
#define INFINI 6000

struct GraphAdjaMatrix {
	char vertexes[MAXVERTEX];
	int edges[MAXVERTEX][MAXVERTEX];
	int numVertexes;
	int numEdges;
};

struct ShortestPath {
	int pathLength;
	int indexOfVertexInPath[MAXVERTEX];
	int numVertex;
};

void createGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix,
	int numVertexes, int numEdges, int edges[][7], char vertexes[]) {
	graphAdjMatrix.numVertexes = numVertexes;
	graphAdjMatrix.numEdges = numEdges;
	
	for (int i = 0; i < numVertexes; i++)
		graphAdjMatrix.vertexes[i] = vertexes[i];

	for (int row = 0; row < numVertexes; row++)
		for (int column = 0; column < numVertexes; column++)
			graphAdjMatrix.edges[row][column] = edges[row][column];
}

void dispalyGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix) {
	cout << "adjacensy matrix :" << endl;
	int row,column;
	printf("%3c",' ');
	for (row = 0; row < graphAdjMatrix.numVertexes; row++)
		printf("%3c",graphAdjMatrix.vertexes[row]);
	printf("\n");
	for (row = 0; row < graphAdjMatrix.numVertexes; row++) {
		printf("%-3c", graphAdjMatrix.vertexes[row]);
		for (column = 0; column < graphAdjMatrix.numVertexes; column++)
			if (graphAdjMatrix.edges[row][column] == INFINI)
				printf("%3s", "∞");
			else
				printf("%3d",graphAdjMatrix.edges[row][column]);
		cout << endl;
	}
}

void DijkstraSolutionShortestPath(GraphAdjaMatrix& graphAdjMatrix,
	ShortestPath allShortestPath[7], int indexStart) {

	for (int i = 0; i < 7; i++) {
		allShortestPath[i].pathLength = graphAdjMatrix.edges[indexStart][i];
		allShortestPath[i].numVertex= 2;
		allShortestPath[i].indexOfVertexInPath[0] = indexStart;
		allShortestPath[i].indexOfVertexInPath[1] = i;
	}//对所有最短路径的信息的初始化，路径长度为0，只包含起点

	bool check[7] = { false };
	check[indexStart] = true;//对已找到和未找到最短路径的顶点分类。初始化

	int pathNum, indexUnCheck, indexCheck;
	ShortestPath pathTemp;
	for (pathNum = 1; pathNum <= graphAdjMatrix.numVertexes - 1; pathNum++) {// 6 条路径
		for (indexUnCheck = 0; indexUnCheck < graphAdjMatrix.numVertexes; indexUnCheck++)  // 所有的顶点
			if (check[indexUnCheck] == false)
				for (indexCheck = 0; indexCheck < graphAdjMatrix.numVertexes; indexCheck++)
					if (indexCheck != indexStart && check[indexCheck] == true)
						if (graphAdjMatrix.edges[indexCheck][indexUnCheck] != INFINI && allShortestPath[indexUnCheck].pathLength > allShortestPath[indexCheck].pathLength + graphAdjMatrix.edges[indexCheck][indexUnCheck]) {
							allShortestPath[indexUnCheck].pathLength = allShortestPath[indexCheck].pathLength + graphAdjMatrix.edges[indexCheck][indexUnCheck];
							
							int k;
							for (k = 0; k < allShortestPath[indexCheck].numVertex; k++)
								allShortestPath[indexUnCheck].indexOfVertexInPath[k] = allShortestPath[indexCheck].indexOfVertexInPath[k];
							allShortestPath[indexUnCheck].indexOfVertexInPath[k] = indexUnCheck;
							allShortestPath[indexUnCheck].numVertex = k + 1;
						}

		pathTemp.pathLength = INFINI;
		for (indexUnCheck = 0; indexUnCheck < graphAdjMatrix.numVertexes; indexUnCheck++)
			if (check[indexUnCheck] == false && allShortestPath[indexUnCheck].pathLength <= pathTemp.pathLength)
				pathTemp = allShortestPath[indexUnCheck];

		check[pathTemp.indexOfVertexInPath[pathTemp.numVertex - 1]] = true;
	}
}

测试结果及对应的图和课本给出的答案如下，可见本程序也是正确的：



谢谢阅读。