迪杰特斯拉算法伪码
程序员文章站
2022-05-22 10:49:49
...
Dijkstra算法有两个核心要点:A、从1为中心出发,B、分为两个集合
求1-->n的最小距离
辅助数据
N : 所有点集合
S : 已计算距离点的集合
M[i][j]: i-->j的距离值,-1表示不可达
D[]:距离数组
D[1] =0,D[i] = +inf,{i!=0}
S= {1}
Count = N
While(--Count>0){
min = +inf
idx = 0
for s in S {
for i in (N-S) {
if M[s][i] !=-1 && min < (M[s][i] + D[s]) {
min = (M[s][i]+D[i])
idx = i
}
}
if idx !=0{
add idx in S
D[idx] = min
}else{
S and N-S is not available
break
}
}
// 时间复杂度为n^3
不断地更新D,不采用笛卡尔积,复杂度下降为n^2,经典的m*n变为了m+n
D[1] =0,D[i] = +inf,{i!=0}
S= {1}
Count = N
While(--Count>0){
min = +inf
idx = 0
for i in (N-S) {
if D[i] < min {
idx = i
}
}
if idx !=0{
add idx in S
D[idx] = min
for i in (N-S) {
if D[i] > D[idx] + M[idx][i] {
D[i] = D[idx] + M[idx][i]
}
}
}else{
S and N-S is not available
break
}
}
上一篇: Gym - 100886B 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest B - Game on Bipartite
下一篇: 2015-2016-petrozavodsk-winter-training-camp-spb-su-spb-au-contest F-Colored Path(状压DP)
推荐阅读
-
Java 迪杰斯特拉算法实现查找最短距离的实现
-
基于Python实现迪杰斯特拉和弗洛伊德算法
-
迪杰斯特拉(Dijkstra)算法(Python)
-
js图数据结构处理 迪杰斯特拉算法代码实例
-
c/c++ 图的最短路径 Dijkstra(迪杰斯特拉)算法
-
迪杰斯特拉算法(Dijkstra)
-
Python实现迪杰斯特拉算法并生成最短路径的示例代码
-
邻接矩阵prim:php实现图的邻接矩阵及普里姆(prim算法),弗洛伊德(floyd),迪杰斯特拉(dijkstra)算法
-
13.GIS中Dijkstra(迪杰斯特拉)算法如何实现?(JavaScript版本有向图)
-
邻接矩阵prim:php实现图的邻接矩阵及普里姆(prim算法),弗洛伊德(floyd),迪杰斯特拉(dijkstra)算法