在图论中，Dijkstra 和 Bellman-Ford 算法是两种常用的单源最短路径算法。Dijkstra 算法适用于无负权边的图，而 Bellman-Ford 算法则可以处理负权边并检测负权回路。

一、Dijkstra 算法（堆优化版）

Dijkstra 算法使用优先队列（通常使用最小堆）来优化查找当前最小距离的顶点。堆优化版 Dijkstra 算法的时间复杂度为 O((V + E) log V)。

1. 算法思想

1. 从源点开始，初始化源点到各顶点的距离，源点到自身的距离为 0，其他顶点距离为无穷大。
2. 使用优先队列（最小堆）维护当前已知的最短路径顶点。
3. 每次从堆中取出距离最小的顶点，更新其邻接顶点的距离。
4. 重复上述步骤直到堆为空。

2. 代码实现

以下是堆优化版 Dijkstra 算法的 C++ 实现：

#include  #include  #include  #include  #include   using namespace std;  const int INF = INT_MAX;  struct Edge {     int to;     int weight; };  void dijkstra(int start, vector>& graph, vector& dist) {     int n = graph.size();     dist.assign(n, INF);     dist[start] = 0;      priority_queue, vector>, greater>> pq;     pq.push({0, start});      while (!pq.empty()) {         int d = pq.top().first;         int u = pq.top().second;         pq.pop();          if (d > dist[u]) continue;          for (auto& edge : graph[u]) {             int v = edge.to;             int weight = edge.weight;             if (dist[u] + weight < dist[v]) {                 dist[v] = dist[u] + weight;                 pq.push({dist[v], v});             }         }     } }  int main() {     int n, m;     cout << "Enter number of vertices and edges: ";     cin >> n >> m;     vector> graph(n);      cout << "Enter edges (u, v, w):" << endl;     for (int i = 0; i < m; ++i) {         int u, v, w;         cin >> u >> v >> w;         graph[u].push_back({v, w});         graph[v].push_back({u, w}); // 如果是有向图，去掉这一行     }      int start;     cout << "Enter start vertex: ";     cin >> start;      vector dist;     dijkstra(start, graph, dist);      cout << "Shortest distances from vertex " << start << ":" << endl;     for (int i = 0; i < n; ++i) {         cout << "Vertex " << i << ": " << dist[i] << endl;     }      return 0; } 

二、Bellman-Ford 算法

Bellman-Ford 算法可以处理包含负权边的图，并且可以检测负权回路。其时间复杂度为 O(VE)。

1. 算法思想

1. 初始化源点到各顶点的距离，源点到自身的距离为 0，其他顶点距离为无穷大。
2. 对所有边进行 V-1 次松弛操作，即对每一条边 (u, v)，如果 dist[u] + weight < dist[v]，则更新 dist[v]。
3. 进行第 V 次松弛操作，如果还能更新任何顶点的距离，则存在负权回路。

2. 代码实现

以下是 Bellman-Ford 算法的 C++ 实现：

#include  #include  #include   using namespace std;  const int INF = INT_MAX;  struct Edge {     int from;     int to;     int weight; };  bool bellman_ford(int start, vector& edges, int n, vector& dist) {     dist.assign(n, INF);     dist[start] = 0;      for (int i = 0; i < n - 1; ++i) {         for (auto& edge : edges) {             if (dist[edge.from] != INF && dist[edge.from] + edge.weight < dist[edge.to]) {                 dist[edge.to] = dist[edge.from] + edge.weight;             }         }     }      for (auto& edge : edges) {         if (dist[edge.from] != INF && dist[edge.from] + edge.weight < dist[edge.to]) {             return false; // 存在负权回路         }     }      return true; }  int main() {     int n, m;     cout << "Enter number of vertices and edges: ";     cin >> n >> m;     vector edges(m);      cout << "Enter edges (u, v, w):" << endl;     for (int i = 0; i < m; ++i) {         cin >> edges[i].from >> edges[i].to >> edges[i].weight;     }      int start;     cout << "Enter start vertex: ";     cin >> start;      vector dist;     if (bellman_ford(start, edges, n, dist)) {         cout << "Shortest distances from vertex " << start << ":" << endl;         for (int i = 0; i < n; ++i) {             cout << "Vertex " << i << ": " << dist[i] << endl;         }     } else {         cout << "Graph contains a negative-weight cycle." << endl;     }      return 0; } 

总结

1. Dijkstra 算法（堆优化版）适用于无负权边的图，使用最小堆优化查找当前最小距离顶点。
2. Bellman-Ford 算法适用于包含负权边的图，可以检测负权回路，但时间复杂度较高。

这两种算法各有优缺点，选择时需根据具体应用场景和图的特性进行权衡。