定义概览
Floyed算法是一种解决所有点对最短路径的算法。虽然Dijkstra算法和Bellman-ford算法解决同样可以解决所有点对最短路径（Dijkstra算法时间复杂度为O(VElogE)，但是不能处理负权边。Bellman-Ford算法时间复杂度为O(V*V*E)），但是Floyed的时间复杂度相对较小为O(V*V*V)且可以处理负权环。
所有点对最短路径
问题描述：在无向有权图G = （V，E）中，假设每条边E[i]的长度是w[i],找到所有顶点到到其余各顶点的最短距离。
算法描述
需要应用动态规划（类似背包）的知识。
首先，对于两个顶点（v，w）的最短路径，无外乎是否经过顶点k两种可能。另一方面，最短路径的子路径仍然是最短路径，比如v-w的最短路径为v ->k->w，那么v-k的最短路径一定是v->k，k-w的最短路径一定是k->w。反过来，如果说一条路径必须要经过点k，那么v-k的最短路径加上k-w的最短路径，一定是v-w的最短路径。
我们将dis[i][j]表示顶点i到顶点j的最短距离。初始化：如果v-w有边，dis[v][w] = vw;dis[v][v] = 0，否则dis[v][w] = oo。
判断v-w的最短路径是否存在k的方法即如果dis[v][k] + dis[k][w] < dis[v][w]，那么dis[v][w] = dis[v][k] + dis[k][w]。
类似与背包问题的思想，逐个判断。
通过判断dis[v][v] < 0? 检测负权环。
代码，在原有基础上修改的写法，不是简洁的写法
#include <iostream>
#include <vector>
#include <fstream>
#define FIN "floyed.in"
#define FOUT "floyed.out"
#define oo ((1LL << 31) - 1)
#define MAXN 50005
using namespace std;
int nodes, edges;
vector<pair<int, int>> Graph[MAXN];
void readData() {
int x, y, cost;
fstream fin(FIN);
fin >> nodes >> edges;
int tmp = edges;
while (tmp--) {
fin >> x >> y >> cost;
Graph[x].push_back({y, cost});
Graph[y].push_back({x, cost});
}
}
bool floyed() {
vector<vector<int>> dis(nodes + 1, vector<int>(nodes + 1, oo));//from 行 to 列
for (int from = 1; from <= nodes; from++) {
for (auto to : Graph[from]) {
dis[from][to.first] = to.second;
}
dis[from][from] = 0;
}
for (int v = 1; v <= nodes; v++) {
for (int i = 1; i <= nodes; ++i) {
for (int j = 1; j <= nodes; ++j) {
if (dis[v][j] != oo && dis[i][v] != oo && dis[i][j] > dis[i][v] + dis[v][j])
dis[i][j] = dis[i][v] + dis[v][j];
}
}
}
for (int i = 1; i <= nodes; ++i) {
for (int j = 1; j <= nodes; ++j) {
cout << i << "->" << j << " : " << dis[i][j] << endl;
}
}
for (int v = 1; v <= nodes; ++v) {
if (dis[v][v] < 0)
return false;
}
return true;
}
int main() {
readData();
floyed();
return 0;
}
原文：https://www.cnblogs.com/zhangzhangtabszj/p/15113813.html