图论算法合集
Floyd-Warshall 算法
介绍
Floyd-Warshall算法是一种用于计算加权图中所有节点对之间最短路径的算法。该算法以动态规划为基础，通过逐步更新最短路径的估计值来找到最终的最短路径。它特别适用于稠密图，即边数接近于节点数平方的图。
步骤详解
-
初始化距离矩阵：
- 创建一个二维数组d，其中d[i][j]表示从节点i到节点j的距离。如果i和j之间有直接边，则d[i][j]是该边的权重，否则d[i][j]设为无穷大。
- 对于所有i，d[i][i]设为0，因为任何节点到其自身的距离都是0。
-
动态规划更新：
- 对于每一个节点k，更新其他所有节点对(i, j)的最短距离。
- 更新规则为：如果从i到j经过k的路径比直接从i到j的路径更短，则更新d[i][j] = d[i][k] + d[k][j]。
-
输出结果：
- 经过更新后，d[i][j]将包含从节点i到节点j的最短路径的距离。
代码实现
#include <bits/stdc++.h>
using namespace std;const int N = 210, INF = 0x3f3f3f3f; // 定义最大节点数和无穷大
int n, m; // 节点数和边数
int d[N][N]; // 距离矩阵int main() {cin >> n >> m;// 初始化距离矩阵，所有距离设为无穷大memset(d, 0x3f, sizeof d);for (int i = 1; i <= n; i++) d[i][i] = 0; // 自己到自己的距离为0// 读入边while (m--) {int a, b, c;cin >> a >> b >> c;d[a][b] = min(d[a][b], c); // 取最小的边权重}// Floyd-Warshall算法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]); // 更新最短距离// 输出任意两点间的最短距离for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++)if (d[i][j] > INF / 2) cout << "INF "; // 超过无穷大的一半表示无路径else cout << d[i][j] << ' ';cout << endl;}return 0;
}
示例
假设有一个图有4个节点和6条边：
- 边1: (1, 2, 2)
- 边2: (1, 3, 6)
- 边3: (2, 3, 3)
- 边4: (2, 4, 1)
- 边5: (3, 4, 1)
- 边6: (4, 1, 5)
初始化距离矩阵
1 2 3 4
1 0 2 6 ∞
2 ∞ 0 3 1
3 ∞ ∞ 0 1
4 5 ∞ ∞ 0
经过第一轮k=1的更新
1 2 3 4
1 0 2 6 ∞
2 ∞ 0 3 1
3 ∞ ∞ 0 1
4 5 7 11 0
经过第二轮k=2的更新
1 2 3 4
1 0 2 5 3
2 ∞ 0 3 1
3 ∞ ∞ 0 1
4 5 7 10 0
经过第三轮k=3的更新
1 2 3 4
1 0 2 5 3
2 ∞ 0 3 1
3 6 8 0 1
4 5 7 10 0
经过第四轮k=4的更新
1 2 3 4
1 0 2 5 3
2 6 0 3 1
3 6 8 0 1
4 5 7 10 0
最终结果表示了所有节点对之间的最短路径长度。
Dijkstra算法
介绍
Dijkstra算法是一种用于计算单源最短路径的算法，即从一个指定的起始节点到图中所有其他节点的最短路径。该算法适用于有向图和无向图，但要求边的权重为非负数。Dijkstra算法利用贪心策略，逐步扩展最短路径树。
步骤详解
-
初始化：
- 设定起点s，初始化距离数组dis，其中dis[s] = 0，其他所有节点的距离初始化为无穷大。
- 使用优先队列（最小堆）来存储和选择当前最近的节点。
-
主循环：
- 每次从优先队列中取出距离最小的节点u，标记为已访问。
- 更新u的所有邻接节点v的距离，如果通过u到v的距离小于当前记录的距离，则更新dis[v]并将v加入优先队列。
-
终止：
- 当所有节点都被访问或优先队列为空时，算法结束。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9 // 定义无穷大int a[105][3], n, m, x, y, s, t;
double mapp[105][105]; // 邻接矩阵表示图
double dis[105]; // 距离数组
bool vis[105]; // 访问标记数组// 计算两点之间的距离
double f(int x1, int y1, int x2, int y2) {return sqrt(double((y2 - y1) * (y2 - y1)) + double((x2 - x1) * (x2 - x1)));
}void Dijkstra() {priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;fill(dis, dis + n + 1, INF); // 初始化距离数组为无穷大pq.push({0, s}); // 起点入队，距离为0dis[s] = 0;while (!pq.empty()) {int u = pq.top().second; // 取出当前距离最小的节点pq.pop();if (vis[u]) continue; // 如果已访问，跳过vis[u] = true; // 标记为已访问for (int j = 1; j <= n; j++) {if (!vis[j] && dis[u] + mapp[u][j] < dis[j]) { // 如果j未访问且通过u到j的距离更短dis[j] = dis[u] + mapp[u][j]; // 更新距离pq.push({dis[j], j}); // 将j入队}}}
}int main() {memset(mapp, 0x7f, sizeof(mapp)); // 初始化图的邻接矩阵为无穷大scanf("%d", &n); // 输入节点数for (int i = 1; i <= n; i++) {scanf("%d %d", &a[i][0], &a[i][1]); // 输入节点的坐标}scanf("%d", &m); // 输入边数for (int i = 0; i < m; i++) {scanf("%d%d", &x, &y);mapp[x][y] = mapp[y][x] = f(a[x][0], a[x][1], a[y][0], a[y][1]); // 计算边的权重}scanf("%d%d", &s, &t); // 输入起点和终点Dijkstra();printf("%.2lf", dis[t]); // 输出从起点到终点的最短距离return 0;
}
示例
假设有一个图有4个节点和4条边：
-
节点1坐标：(0, 0)
-
节点2坐标：(2, 2)
-
节点3坐标：(5, 5)
-
节点4坐标：(7, 8)
-
边1: (1, 2)
-
边2: (2, 3)
-
边3: (3, 4)
-
边4: (4, 1)
每条边的权重由节点间的欧几里得距离计算得出。
初始化邻接矩阵
1 2 3 4
1 0 2.83 ∞ ∞
2 2.83 0 4.24 ∞
3 ∞ 4.24 0 3.61
4 ∞ ∞ 3.61 0
Dijkstra算法过程
- 起点为1，距离初始化为：dis = [0, 2.83, ∞, ∞]，节点1入队。
- 节点1出队，标记为已访问。更新节点2的距离。
- 节点2出队，标记为已访问。更新节点3的距离。
- 节点3出队，标记为已访问。更新节点4的距离。
- 最终，dis = [0, 2.83, 7.07, 10.68]，节点4的最短距离为10.68。
总结
Floyd-Warshall算法适用于计算所有节点对之间的最短路径，时间复杂度为O(n^3)，适用于稠密图。Dijkstra算法用于计算单源最短路径，时间复杂度为O((V+E) log V)，适用于边权非负的稀疏图。
通过实际代码示例和详尽的注释，我们理解了两种算法的核心思想和实现细节。在实际应用中，根据问题的性质选择合适的算法可以提高效率和准确性。
