Dijkstra算法是单源最短路径经典算法，一般用于所有边的权为非负数的情况下，有向图和无向图均可。
效率方面：存储图模型的数据结构有很多种，使用邻接矩阵的话其空间复杂度都为O(E^2)。而如果是稀疏图，使用邻接链表更划算，空间复杂度为O(V+E)。在每次搜索离起点最近的点方面，这里用的还是vector（最近在复习vector….），所以每一次的时间复杂度还是O(N)，其实可以使用优先队列实现，将时间复杂度降到O(logN)。
路径数目方面：一般算法使用一个一维数组记录每个点的前驱点，以此记录指定点到每个点的最短路径。但是由于每个点只保留一个前驱点，因此最后得到的最短路径只有一条，寻找过程中其他距离相等的最短路径会被抛弃，而做到保存多条最短路径，可以让每一个点都维护一个自己的前驱点数组。对于点i，在遇到距离相同的路径的时候，把i在这条路径的前驱点记录下来，而不是抛弃或者覆盖；而遇到更短的路径的时候，把i的前驱点数组清空，存入新的前驱点。这样最后每个点的前驱数组大小都不同。
/** * * @param start 起点 * @param dest 终点 * @param adj 邻接链表。adj[i][k]表示节点i的第k个邻接点的索引 * @param distance 到起点的距离。distance[i]表示起点到点i的距离 * @return prevPoints 前驱点数组。 prevPoints[k]表示到达点k的最短路径中的所有前驱点 */ vector<vector<int> > dijkstra(vector<vector<int> > adj，int start, int dest=-2， vector<int> distance) { unsigned long num = adj.size(); vector<bool> visited(num, false); visited[start] = true; vector<vector<int> > prevPoints; //前驱点数组初始化 for (int i = 0; i < num; ++i) { if (distance[i] < 999) { prevPoints.push_back(vector<int>(1,start)); } else{ prevPoints.push_back(vector<int>(1,-1)); } } if (prevPoints[dest][0] == start) { return prevPoints; } for (int i = 1; i < num; ++i) { // 找离起点最近的点 // 这里的复杂度还是O(N)，可以通过使用优先队列优化 int closest = 999; int toVisit = -1; for (int j = 0; j < num; ++j) { if (!visited[j] && distance[j] < closest) { closest = distance[j]; toVisit = j; } } //如果是要找指定终点dest，可以提前剪枝， //但这样的话未访问的点的路径就不能保证是最短的。 if (toVisit != -1 && !(dest != -2 && toVisit == dest) ) { //更新最短路径 visited[toVisit] = true; for (int k = 0; k < adj[toVisit].size(); k++) { if (adj[toVisit][k] != -1 && !visited[adj[toVisit][k]]) { if (distance[adj[toVisit][k]] > distance[toVisit] + 1) { //update the distance distance[adj[toVisit][k]] = distance[toVisit] + 1; //clear the paths,and store the new path prevPoints[adj[toVisit][k]].clear(); prevPoints[adj[toVisit][k]].push_back(toVisit); } else if (distance[adj[toVisit][k]] == distance[toVisit] + 1) { //add the new path prevPoints[adj[toVisit][k]].push_back(toVisit); } } } } else { break; } } return prevPoints; }得到的前驱点数组可以用DFS从终点往回获取。
if (prevPoints[dest][0] != -1){ index = dest; results = getPaths(start,index,prevPoints); } /** * * @param start 起点 * @param index 终点 * @param prevPoints 前驱点数组。prevPoints[k]表示到达点k的最短路径中的所有前驱点 * @return paths 路径。paths[k]表示从start到index的第k条最短路径 */ vector<vector<int> > getPaths(int start,int index, vector<vector<int> >& prevPoints){ vector<vector<int> >childPaths; vector<vector<int> >midPaths; if (index != start){ for (int i = 0; i < prevPoints[index].size(); ++i) { childPaths = getPaths(start,prevPoints[index][i],prevPoints); for (int j = 0; j < childPaths.size(); ++j) { childPaths[j].push_back(index); } if(midPaths.empty()){ midPaths = childPaths; } else{ midPaths.insert(midPaths.end(),childPaths.begin(),childPaths.end()); } } } else{ // 第一个点 midPaths.push_back(vector<int>(1,start)); } return midPaths; }