多源最短路径Floyd算法(有向图)
时间: 2023-02-27 16:41:39 浏览: 52
Floyd算法是一种用于求多源最短路径的算法,特别适用于有向图。它的基本思想是使用动态规划的方法,通过重复计算最短路径来逐步更新每两点间的最短距离。具体来说,Floyd算法需要三重循环来实现,分别是:
1. 遍历所有的中间点;
2. 遍历所有的起点;
3. 遍历所有的终点。
每次循环都会更新从起点到终点的最短路径,最终得到所有点对间的最短路径。
Floyd算法的时间复杂度为O(n^3),其中n是图中点的数量,因此对于大型图来说,Floyd算法可能不太适用,但它对于较小的图来说却是非常有效的。
相关问题
编写代码首先用数组初始化有向图,邻接矩阵建立有向有权重图(CreateGraph 函数),然 后分别用 Dijkstra 算法求单源最短路径和 Floyd-Warshall 算法求出多源最短路径。
好的,下面是一个简单的代码示例,其中包括创建有向图和 Dijkstra 算法、Floyd-Warshall 算法的实现:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1005; // 最大顶点数
const int INF = 0x3f3f3f3f; // 无穷大
struct Edge { // 边的结构体
int to; // 终点
int w; // 权重
Edge(int _to, int _w) : to(_to), w(_w) {}
};
vector<Edge> G[MAXN]; // 邻接表存储图
int n, m; // 顶点数、边数
int dist[MAXN]; // 存储 Dijkstra 算法中的最短距离
int d[MAXN][MAXN]; // 存储 Floyd-Warshall 算法中的最短距离
// 初始化有向图,邻接矩阵建立有向有权重图
void CreateGraph() {
cin >> n >> m;
memset(d, INF, sizeof(d)); // 初始化 Floyd-Warshall 矩阵
while (m--) {
int u, v, w;
cin >> u >> v >> w;
G[u].push_back(Edge(v, w)); // u -> v,权重为 w,加入邻接表
d[u][v] = min(d[u][v], w); // 更新 Floyd-Warshall 矩阵
}
}
// Dijkstra 算法求单源最短路径
void Dijkstra(int s) {
memset(dist, INF, sizeof(dist));
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push(make_pair(0, s));
while (!q.empty()) {
auto p = q.top();
q.pop();
int d = p.first; // 当前点到起点的距离
int v = p.second; // 当前点的编号
if (dist[v] < d) continue;
for (int i = 0; i < G[v].size(); i++) {
Edge e = G[v][i];
if (dist[e.to] > dist[v] + e.w) {
dist[e.to] = dist[v] + e.w;
q.push(make_pair(dist[e.to], e.to));
}
}
}
}
// Floyd-Warshall 算法求多源最短路径
void FloydWarshall() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
int main() {
CreateGraph();
Dijkstra(1); // 求从起点 1 到其他所有点的最短距离
for (int i = 1; i <= n; i++) {
cout << dist[i] << ' ';
}
cout << endl;
FloydWarshall(); // 求任意两点间的最短距离
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << d[i][j] << ' ';
}
cout << endl;
}
return 0;
}
```
以上是一个简单的实现,你可以根据自己的需要进行修改和优化。希望能够帮到你!
最短路劲Floyd算法
Floyd算法是一种多源最短路径算法,用于计算图中任意两个顶点之间的最短路径。它通过动态规划的思想逐步更新路径的长度来计算最短路径。
Floyd算法的基本思想是通过一个中间顶点集合,逐个考察这个集合中的顶点,看是否可以通过这个中间顶点缩短路径长度。具体步骤如下:
1. 初始化一个二维数组D,其中D[i][j]表示顶点i到顶点j的最短路径长度。如果i和j之间有边相连,则D[i][j]为边的权值,否则为无穷大。
2. 对于每一个中间顶点k,考虑所有的一对顶点i和j,更新D[i][j]为D[i][k] + D[k][j]与D[i][j]的较小值。
3. 重复步骤2,不断更新D数组,直到所有顶点都被考虑为中间顶点。
4. 最后得到的D数组中,D[i][j]表示顶点i到顶点j的最短路径长度。
Floyd算法的时间复杂度为O(V^3),其中V为图中顶点的个数。因此,Floyd算法适用于顶点数不太多的图。
需要注意的是,Floyd算法可以处理有向图和带负权边的图,但不能处理带有负权环的图,因为负权环会导致最短路径不存在。
总结起来,Floyd算法是一种多源最短路径算法,通过动态规划的思想逐步更新路径长度,可以计算出图中任意两个顶点之间的最短路径长度。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [图算法——求最短路径(Floyd算法)](https://blog.csdn.net/qq_61959780/article/details/129363941)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [最短路径(Dijkstra算法和Floyd算法)](https://blog.csdn.net/weixin_44267007/article/details/119770562)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]