获取多条最短路径的Dijkstra算法

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;
}

最后

以上就是暴躁酒窝为你收集整理的获取多条最短路径的Dijkstra算法的全部内容，希望文章能够帮你解决获取多条最短路径的Dijkstra算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。