最短路算法

最短路算法

   数据结构 10 分钟读完 (大约1536个字) 0次访问
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include"MGraph.h"
//-----------------最短路算法--------------//
// 采用邻接矩阵存储表示
//-----------------Dijkstra算法求最短路径--------------//
Status DijsMinPath(MGraph G, int v0);
Status DispDijsPaths(MGraph G, int *D, int *fa, bool *final, int v0);
Status MinDijsPrint(MGraph G, int *fa, int v, int v0);
//-----------------Floyd算法求最短路径--------------//
Status FloydMinPath(MGraph G);
Status MinFloydPrint(MGraph G, int *path, int v, int w); 
Status DispFloydPaths(MGraph G, int *D, int *path);
int main()
{
    MGraph G;
    CreateGraph(G);
    GraphPrint(G);
    cout << "----------------------Dijkstra MinPath Problem Page------------------\n";
    cout << "Input the source node: ";
    VertexType sv;
    cin >> sv;
    int v0 = LocateVex(G, sv);
    DijsMinPath(G, v0);
    cout << "-----------------------Floyd MinPath Problem Page---------------------\n";
    FloydMinPath(G);
    return 0;
}
/*-------------------------------Dijkstra ALgorithm-----------------------*/
Status DijsMinPath(MGraph G, int v0)
{
    // D[v]表示v0到v的最短路径带权长度
    // fa[v]=w表示通过w中转，即D(v0,w)+arc(w,v)便于回溯路径
    // final[v]：标识数组，为True当且仅当v属于S, 即已经求得v0到v最短路
    int fa[Max_Vertex_Num], D[Max_Vertex_Num];
    bool final[Max_Vertex_Num];
    int v = 0, w = 0, i = 0;
    // 初始化操作
    inp(v,0, G.vexnum-1){
        final[v] = false;  
        D[v] = G.arcs[v0][v].adj;
        // v0到v邻接
        if(D[v] != INFINITY) fa[v] = v0; // 路径回溯
    }

    final[v0] = true;   // 初始化节点v0属于S集
    // 取min(d(v0,v)) v属于V-S, 即求剩余节点中到v0距离最短得节点v
    inp(i,1,G.vexnum-1){
        // 当前所知离v0顶点的最近距离, 初始未找到为无穷大
        int min_path = INFINITY;   
        inp(w,0,G.vexnum-1){
            if(!final[w])    // w节点在V-S中
                if(D[w] < min_path){  // 取min
                    v = w;  
                    min_path = D[w];
                }
        }
        // 将选中的节点即确定距离得节点加入S集中
        if(min_path != INFINITY) final[v] = true;  
        else break;
        // 通过新选的节点v中转更新V-S中节点距离操作
        inp(w,0,G.vexnum-1){
            if(!final[w] && G.arcs[v][w].adj != INFINITY)    // 避免最大值上溢问题的特判
                if(min_path + G.arcs[v][w].adj < D[w]){
                    D[w] = min_path + G.arcs[v][w].adj;
                    fa[w] = v;    // 上次中转节点  
                }
        }
    }
    DispDijsPaths(G, D, fa, final, v0);
    return true;
}
Status DispDijsPaths(MGraph G, int *D, int *fa, bool *final, int v0)
{  
    int i = 0;
    inp(i, 0, G.vexnum-1){
        if(i != v0){   // 不包括源点
	        if(final[i]){    // 如果已确定最短距离
                cout << "from " << G.vexs[v0] << " to " << G.vexs[i] << " the shortest path length: " << D[i];
                cout << endl << "Display the path:\n" << G.vexs[v0] << "->"; /*输出路径上的起点*/
                MinDijsPrint(G, fa, i, v0);	/*输出路径上的中间点*/
                cout << G.vexs[i] << endl;	/*输出路径上的终点*/
            }
            else cout << "from " << G.vexs[v0] << " to " << G.vexs[i] << " there is no road.\n";
	   }  
    }
    return true;
}
Status MinDijsPrint(MGraph G, int *fa, int v, int v0)
{
    // 回溯输出v到v0的最短路径
    int w = fa[v];
    if(w == v0){
        return true;  // 找到了起点则返回
    }
    MinDijsPrint(G, fa, w, v0);   // 找w顶点的父顶点
    cout << G.vexs[w] << "->";
    return true;
}
/*-------------------------------Dijkstra ALgorithm-----------------------*/

/*-------------------------------Floyd ALgorithm--------------------------*/
Status FloydMinPath(MGraph G)
{  
    // path[v][w]表示v到w最短路径上经过的最后一个节点即w的父节点
    int path[G.vexnum][G.vexnum], D[G.vexnum][G.vexnum];
    int i = 0, j = 0, k = 0;
    inp(i, 0, G.vexnum-1)    //矩阵 D与 path初始化
        inp(j, 0, G.vexnum-1){
            D[i][j] = G.arcs[i][j].adj;
            if(D[i][j] != INFINITY)  path[i][j] = i;     // 头节点 	  
	        else path[i][j] = -1;	    // i到j无路径
        }
  
    // 生成D(k)及path(k)
    inp(k, 0, G.vexnum-1)
        inp(i, 0, G.vexnum-1)
            inp(j, 0, G.vexnum-1)
                // 加入Vk节点
                if(D[i][k] != INFINITY && D[k][j] != INFINITY)    // 解决INF运算溢出的问题
                    if(D[i][j] > D[i][k] + D[k][j]){ 
                        D[i][j] = D[i][k] + D[k][j];
                        path[i][j] = path[k][j];   //缩短路径长度, 经过 k 到 j
                        //注解：相当于对<i,j>路径改向，<i,j>方向改为经k的<k,j>方向
                    }
    DispFloydPaths(G, &D[0][0], &path[0][0]);
    return true;
}
Status DispFloydPaths(MGraph G, int *D, int *path)
{  
    int i = 0, j = 0, k = 0;
    inp(i,0,G.vexnum-1){
        cout << "-------------------------------------------------------------\n";
        inp(j,0,G.vexnum-1){
            if(i == j) continue;     // 不包括节点自身
            if(D[i*G.vexnum + j] != INFINITY){
                cout << "from " << G.vexs[i] << " to " << G.vexs[j] << " the shortest path length: " << D[i*G.vexnum + j] << endl;
                cout << "Display the path:\n" << G.vexs[i] << "->"; /*输出路径上的起点*/
                MinFloydPrint(G, path, i, j);	/*输出路径上的中间点*/
                cout << G.vexs[j] << endl;	/*输出路径上的终点*/
            }
            else cout << "from " << G.vexs[i] << " to " << G.vexs[j] << " there is no road.\n";
        }
        cout << "-------------------------------------------------------------\n";
    }
    return true;
}
Status MinFloydPrint(MGraph G, int *path, int v, int w)  
{
    // 回溯输出v到w的最短路径
    int p = path[v*G.vexnum + w];
    if(p == v){
        return true;  // 找到了起点则返回
    }
    MinFloydPrint(G, path, v, p);   // 找w顶点的父顶点
    cout << G.vexs[p] << "->";
    return true;
}
/*-------------------------------Floyd ALgorithm--------------------------*/

一个算例演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*
Input the type of graph(0:DG,1:DN,2:UDG,3:UDN):
1
Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):
6 8 0
Input Graph Node Sign:
V0 V1 V2 V3 V4 V5
Input two vertices and weight of the edges:
V0 V5 100
V0 V4 30
V0 V2 10
V1 V2 5 
V4 V5 60
V4 V3 20
V3 V5 10
V2 V3 50
Output Graph Information:
Graph Kind: directed nets
Vextices number: 6   Arcs number: 8
Vextices Vector Information:
V0-<0>-V0 V0-<10>-V2 V0-<30>-V4 V0-<100>-V5   
V0  Vextice Degree: 5  Outdegree: 4  Indegree: 1
V1-<0>-V1 V1-<5>-V2
V1  Vextice Degree: 3  Outdegree: 2  Indegree: 1
V2-<0>-V2 V2-<50>-V3
V2  Vextice Degree: 5  Outdegree: 2  Indegree: 3
V3-<0>-V3 V3-<10>-V5
V3  Vextice Degree: 5  Outdegree: 2  Indegree: 3
V4-<20>-V3 V4-<0>-V4 V4-<60>-V5
V4  Vextice Degree: 5  Outdegree: 3  Indegree: 2
V5-<0>-V5
V5  Vextice Degree: 5  Outdegree: 1  Indegree: 4
----------------------Dijkstra MinPath Problem Page------------------
Input the source node: V0
from V0 to V1 there is no road.
from V0 to V2 the shortest path length: 10
Display the path:
V0->V2
from V0 to V3 the shortest path length: 50
Display the path:
V0->V4->V3
from V0 to V4 the shortest path length: 30
Display the path:
V0->V4
from V0 to V5 the shortest path length: 60
Display the path:
V0->V4->V3->V5
-----------------------Floyd MinPath Problem Page---------------------
-------------------------------------------------------------
from V0 to V1 there is no road.
from V0 to V2 the shortest path length: 10
Display the path:
V0->V2
from V0 to V3 the shortest path length: 50
Display the path:
V0->V4->V3
from V0 to V4 the shortest path length: 30
Display the path:
V0->V4
from V0 to V5 the shortest path length: 60
Display the path:
V0->V4->V3->V5
-------------------------------------------------------------
-------------------------------------------------------------
from V1 to V0 there is no road.
from V1 to V2 the shortest path length: 5
Display the path:
V1->V2
from V1 to V3 the shortest path length: 55
Display the path:
V1->V2->V3
from V1 to V4 there is no road.
from V1 to V5 the shortest path length: 65
Display the path:
V1->V2->V3->V5
-------------------------------------------------------------
-------------------------------------------------------------
from V2 to V0 there is no road.
from V2 to V1 there is no road.
from V2 to V3 the shortest path length: 50
Display the path:
V2->V3
from V2 to V4 there is no road.
from V2 to V5 the shortest path length: 60
Display the path:
V2->V3->V5
-------------------------------------------------------------
-------------------------------------------------------------
from V3 to V0 there is no road.
from V3 to V1 there is no road.
from V3 to V2 there is no road.
from V3 to V4 there is no road.
from V3 to V5 the shortest path length: 10
Display the path:
V3->V5
-------------------------------------------------------------
-------------------------------------------------------------
from V4 to V0 there is no road.
from V4 to V1 there is no road.
from V4 to V2 there is no road.
from V4 to V3 the shortest path length: 20
Display the path:
V4->V3
from V4 to V5 the shortest path length: 30
Display the path:
V4->V3->V5
-------------------------------------------------------------
from V5 to V0 there is no road.
from V5 to V1 there is no road.
from V5 to V2 there is no road.
from V5 to V3 there is no road.
from V5 to V4 there is no road.
-------------------------------------------------------------
*/

最短路算法

https://markstiff.github.io/数据结构/最短路算法/

作者

Mark Stiff

发布于

2022-11-04

更新于

2024-01-21

许可协议

 

喜欢这篇文章？打赏一下作者吧

评论

  关注我

分类

标签

Generative Model1
Latex3
Markdown1
二叉树1
人工智能1
体系结构1
图论2
字符串1
嵌入式2
嵌入式系统1
排序4
数字信号处理1
数学6
数据库系统1
数据结构16
数据结构与算法 - LeetCode1
概率论与数理统计 - 数学1
稀疏矩阵3
算法3
算法竞赛3
计算机原理4
软件工程1
×