数据结构之最短路径(2) [弗洛伊德算法]

78 阅读 0 评论 52 点赞

我是靠谱客的博主靓丽小鸽子，最近开发中收集的这篇文章主要介绍数据结构之最短路径(2) [弗洛伊德算法]，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【1】为什么需要弗洛伊德算法？

带权图中单个源点到所有顶点的最短路径问题可以用《迪杰斯特拉算法》求解。

那如果要求图中每一个顶点与其它顶点之间的最短路径呢？类似可以想到的方法为：

每次以一个顶点为源点，重复执行地杰斯特拉算法算法n次。

这样，理论上我们便可以求得每一个顶点与其它顶点的最短路径，总的执行时间为O(n3）。

好吧！为了实现这个中需求，可以采用另外一种求解算法：弗洛伊德算法。

为了更好的理解弗洛伊德算法的精妙，我们先看简单的案例。

如下图是一个最简单的3个顶点连通网图:

附上dist数组与prev数组：(左边为dist 右边为prev)

【2】弗洛伊德算法

弗洛伊德算法是非常漂亮的算法，简洁直观大气上档次。

不过很可惜由于它的三重循环，因此也是O(n*n*n)的时间复杂度。

如果你面临需要求所有顶点至所有顶点的最短路径问题？

它是很好的选择。

[如果上面的不太懂那就直接看代码就好啦，代码更容易懂一些]

代码如下：

 1 #include "stdafx.h"
 2 #include<iostream>
 3 #include<string>
 4 #define MAX_VERTEX_NUM 100
 5 #define INFINITY 65535
 6 typedef int Pathmatirx[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 7 typedef int ShortPathTable[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 8 using namespace std;
 9 typedef struct Graph
//有向图的邻接矩阵
10 {
11
char vexs[MAX_VERTEX_NUM];
//存放顶点的数组
12
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//定义一个临界矩阵
13
int vexnum, arcnum;
//总顶点数、总边数
14 }Graph;
15
16 int LocateVex(Graph G, char ch) //搜索
17 {
18
for (int i = 0; i < G.vexnum; i++)
19
if (G.vexs[i] == ch)
20
return i;
21
return -1;
22 }
23
24 void CreateGraph(Graph &G)
//创建无向图
25 {
26
char c1, c2;
//弧尾、弧头
27
int i, j, weight;
//weight为权重
28
cout << "请输入总顶点数、总边数(空格隔开):";
29
cin >> G.vexnum >> G.arcnum;
30
cout << "请输入顶点信息(空格隔开):" << endl;
31
for (i = 0; i < G.vexnum; i++)
32 
{
33
cin >> G.vexs[i];
34 
}
35
for (i = 0; i < G.vexnum; i++)
36
for (j = 0; j < G.vexnum; j++)
37
G.arcs[i][j] = INFINITY;
38
cout << "请输入弧尾、弧头以及权值:" << endl;
39
for (int k = 0; k < G.arcnum; k++)
40 
{
41
cin >> c1 >> c2 >> weight;
42
i = LocateVex(G, c1);
43
j = LocateVex(G, c2);
44
G.arcs[i][j] = weight;
45 
}
46 }
47
48 void ShortestPath_Floyd(Graph G, int prev[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM])
49 {
//Floyd算法，求网图G中个顶点v到其余顶点w最短路径prev[v][w]及带权长度dist[v][w]
50
int v, w, k;
51
for (v = 0; v < G.vexnum; v++)
52
for (w = 0; w < G.vexnum; w++)
//初始化dist与prev
53 
{
54
dist[v][w] = G.arcs[v][w];
//dist[v][w]值即为对应点间的权值
55
prev[v][w] = w;
//初始化prev
56 
}
57
for (k = 0; k < G.vexnum; k++)
//更新路径
58
for (v = 0; v < G.vexnum; v++)
59
for (w = 0; w < G.vexnum; w++)
60
{
//如果经过下标为k顶点路径比原两点间路径更短
61
if (dist[v][w] > dist[v][k] + dist[k][w])
62 
{
63
dist[v][w] = dist[v][k] + dist[k][w];
64
prev[v][w] = prev[v][k];
//路径设置经过下标为k的顶点
65 
}
66 
}
67
for (v = 0; v < G.vexnum; v++)
//输出函数
68 
{
69
for (w = v + 1; w < G.vexnum; w++)
70 
{
71
cout << G.vexs[v] << " - " << G.vexs[w] << " weight: " << dist[v][w]<<" ";
72
int k = prev[v][w];
73
cout << "path: " << G.vexs[v];
74
while (k != w)
75 
{
76
cout << "->" << G.vexs[k];
77
k = prev[k][w];
78 
}
79
cout << "->" << G.vexs[w]<<" ";
80 
}
81
cout << endl;
82 
}
83 }
84
85 int main()
86 {
87 
Graph G;
88
int prev[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
89
int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
90
int v0;
91 
CreateGraph(G);
92 
ShortestPath_Floyd(G, prev, dist);
93
94 }