最短路径问题
最短路径问题是图论中的一个经典问题,旨在寻找从一个起点到一个终点的最短路径。最常见的算法包括Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法。这些算法被广泛用于导航系统、网络路由等领域。
问题描述
- 输入: 一个加权图,表示图中各节点之间的连接和权重,以及一个起始节点。
- 输出: 从起始节点到其他所有节点的最短路径长度。
代码实现
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
class ShortestPath {
public:
// Dijkstra算法实现(适用于非负权重图)
vector<int> dijkstra(int n, vector<vector<pair<int, int>>> &graph, int start) {
vector<int> dist(n, INT_MAX);
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
int d = pq.top().first;
pq.pop();
if (d > dist[u]) continue;
for (auto &edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
return dist;
}
// Bellman-Ford算法实现(适用于有负权重的图)
vector<int> bellmanFord(int n, vector<vector<pair<int, int>>> &graph, int start) {
vector<int> dist(n, INT_MAX);
dist[start] = 0;
for (int i = 1; i < n; i++) {
for (int u = 0; u < n; u++) {
for (auto &edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
}
// 检查是否存在负权重环
for (int u = 0; u < n; u++) {
for (auto &edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
cout << "Graph contains a negative-weight cycle" << endl;
return {};
}
}
}
return dist;
}
};
int main() {
int n, m, start;
cout << "Enter the number of vertices: ";
cin >> n;
思路分析
类的设计
ShortestPath
类封装了求解最短路径问题的两种常见算法:Dijkstra算法和Bellman-Ford算法。
这种设计使得两种算法可以独立实现和测试,并根据不同的图特性选择合适的算法。
Dijkstra算法
dijkstra()
方法使用优先队列(最小堆)来高效地选择当前距离最短的节点,并更新其邻接节点的最短距离。
这种方法适用于没有负权重的图,时间复杂度为O(E log V)
,其中E为边的数量,V为顶点的数量。
Bellman-Ford算法
bellmanFord()
方法适用于含有负权重的图,并且可以检测负权重环的存在。
算法的时间复杂度为O(V * E)
,在图的稠密度较高时效率较低,但在处理负权重时有其优势。