数据结构与C++ 知识量:9 - 32 - 91
单源点的最短路径是指从给定的源点出发,到图中所有其他顶点的最短路径。在图论中,单源点的最短路径问题是一个经典的算法问题,通常使用Dijkstra算法或Bellman-Ford算法来解决。
Dijkstra算法是一种贪心算法,它从源点开始,每次选择一条到源点距离最短的边,然后更新通过这条边到达的顶点的距离。这个过程一直重复,直到所有顶点都被访问过。Dijkstra算法的时间复杂度为O((V+E)logV),其中V是顶点数,E是边数。
Bellman-Ford算法则是另一种求解单源点最短路径的算法,它通过动态规划的思想,从源点开始逐步计算到其他顶点的最短路径。Bellman-Ford算法可以处理带有负权边的图,并且能够检测到负权环。它的时间复杂度为O(V*E),其中V是顶点数,E是边数。
无论是Dijkstra算法还是Bellman-Ford算法,求解单源点的最短路径都需要将图中的所有顶点和边存储在计算机中,并且需要编写相应的算法程序来执行计算。在实际应用中,单源点的最短路径问题可以应用于各种场景,如网络路由、交通规划、物流配送等。
以下是一个使用C++描述的Dijkstra算法的示例:
#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; const int MAX_N = 100; // 最大节点数 vector<pair<int, int>> adj[MAX_N]; // 邻接表 int dist[MAX_N]; // 存储从起点到各顶点的最短距离 bool vis[MAX_N]; // 记录顶点是否被访问过 void dijkstra(int start) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 存储边的最小堆,按照权值从小到大排序 fill(dist, dist + MAX_N, INT_MAX); // 初始化距离数组为无穷大 dist[start] = 0; // 将起点到起点的距离设为0 pq.push(make_pair(0, start)); // 将起点加入最小堆中 vis[start] = true; // 将起点标记为已访问 while (!pq.empty()) { int u = pq.top().second; // 取出最小堆中的最小权值边起点 pq.pop(); for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i].first; int w = adj[u][i].second; if (!vis[v] && dist[v] > dist[u] + w) { // 如果顶点v未被访问过,且从起点到v的距离小于当前最小距离,则更新最小距离和最小堆 dist[v] = dist[u] + w; pq.push(make_pair(dist[v], v)); // 将边加入最小堆中 vis[v] = true; // 将顶点v标记为已访问 } } } for (int i = 0; i < MAX_N; i++) { // 输出最短路径中的边和权值 if (dist[i] == INT_MAX) { cout << "No path to node " << i << endl; } else { cout << "Shortest path from node " << start << " to node " << i << ": "; int prev = -1; for (int j = start; j != i; j = prev) { if (vis[j] && prev != -1) { // 如果顶点j被访问过,且j不是起点,则输出边和权值 cout << j << " - " << prev << " " << dist[i] - dist[j] << endl; } prev = j; // 更新prev为当前顶点j的上一个顶点 } cout << i << endl; // 输出终点i } } }
要计算每对顶点之间的最短路径,可以使用Floyd-Warshall算法。该算法可以在O(V^3)的时间复杂度内计算出所有顶点对之间的最短路径。
Floyd-Warshall算法的基本思想是通过动态规划的方式,逐步计算出每个顶点到其他顶点的最短路径。算法的核心是利用中间顶点来逼近最短路径,通过不断更新距离矩阵来逐步逼近最短路径。
以下是一个使用C++实现Floyd-Warshall算法的示例代码:
#include <iostream> #include <vector> #include <climits> using namespace std; const int MAX_N = 100; // 最大节点数 vector<vector<int>> dist(MAX_N, vector<int>(MAX_N, INT_MAX)); // 存储从起点到各顶点的最短距离 void floydWarshall() { for (int k = 0; k < MAX_N; k++) { for (int i = 0; i < MAX_N; i++) { for (int j = 0; j < MAX_N; j++) { if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; // 更新最短距离 } } } } } int main() { // 初始化距离矩阵,这里假设有4个节点,节点之间的距离如下: // 0 1 2 3 // 1 0 3 2 // 4 2 0 1 // 3 1 5 0 dist[0][1] = 1; dist[0][2] = 4; dist[0][3] = 3; dist[1][0] = 1; dist[1][2] = 2; dist[1][3] = 1; dist[2][0] = 4; dist[2][1] = 2; dist[2][3] = 1; dist[3][0] = 3; dist[3][1] = 1; dist[3][2] = 5; floydWarshall(); // 调用Floyd-Warshall算法计算最短路径 // 输出结果,这里假设要查询节点0到节点3的最短路径长度,可以直接输出dist[0][3]的值即可。如果要输出完整的路径,需要额外实现一个回溯函数来追踪路径。 cout << "Shortest path length from node 0 to node 3: " << dist[0][3] << endl; return 0; }
Copyright © 2017-Now pnotes.cn. All Rights Reserved.
编程学习笔记 保留所有权利
MARK:3.0.0.20240214.P35
From 2017.2.6