贝尔曼福特算法,分别用C语言，C++,java,python编写出来

源码资源网

贝尔曼福特算法是求解单元最短路径问题的一种算法，由理查德贝尔曼和莱斯特福特创立的。有时候这种算法也被称为Moore-Bellman-ford算法，因为Edward F . Moore也为这个算法的发展做出了贡献。

它的原理是对图进行|V|-1次松弛操作，得到所有可能的最短路径。其优于迪克斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(|V||E|）。但算法可以进行若干种优化，提高了效率。

贝尔曼福特算法,分别用C语言，C++,java,python编写出来
下面是贝尔曼福特算法（Bellman-Ford Algorithm）的不同语言实现示例：
1. C语言：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <limits.h>
   
4. struct Edge {
   
5.     int src, dest, weight;
   
6. };
   
7. struct Graph {
   
8.     int V, E;
   
9.     struct Edge* edge;
   
10. };
    
11. struct Graph* createGraph(int V, int E) {
    
12.     struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    
13.     graph->V = V;
    
14.     graph->E = E;
    
15.     graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
    
16.     return graph;
    
17. }
    
18. void BellmanFord(struct Graph* graph, int src) {
    
19.     int V = graph->V;
    
20.     int E = graph->E;
    
21.     int dist[V];
    
22.      for (int i = 0; i < V; i++)
    
23.         dist[i] = INT_MAX;
    
24.     dist[src] = 0;
    
25.      for (int i = 1; i <= V - 1; i++) {
    
26.         for (int j = 0; j < E; j++) {
    
27.             int u = graph->edge[j].src;
    
28.             int v = graph->edge[j].dest;
    
29.             int weight = graph->edge[j].weight;
    
30.             if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
    
31.                 dist[v] = dist[u] + weight;
    
32.         }
    
33.     }
    
34.      for (int i = 0; i < E; i++) {
    
35.         int u = graph->edge[i].src;
    
36.         int v = graph->edge[i].dest;
    
37.         int weight = graph->edge[i].weight;
    
38.         if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
    
39.             printf("Graph contains negative weight cycle\n");
    
40.             return;
    
41.         }
    
42.     }
    
43.      printf("Vertex\tDistance from Source\n");
    
44.     for (int i = 0; i < V; i++)
    
45.         printf("%d\t%d\n", i, dist[i]);
    
46. }
    
47. 
    

复制代码

游客，本帖隐藏的内容需要积分高于 9 才可浏览，您当前积分为 0

2. C++:

1. #include <iostream>
   
2. #include <climits>
   
3. #include <vector>
   
4. struct Edge {
   
5.     int src, dest, weight;
   
6. };
   
7. struct Graph {
   
8.     int V, E;
   
9.     std::vector<Edge> edges;
   
10. };
    
11. void BellmanFord(Graph graph, int src) {
    
12.     int V = graph.V;
    
13.     int E = graph.E;
    
14.     std::vector<int> dist(V, INT_MAX);
    
15.     dist[src] = 0;
    
16.      for (int i = 1; i <= V - 1; i++) {
    
17.         for (int j = 0; j < E; j++) {
    
18.             int u = graph.edges[j].src;
    
19.             int v = graph.edges[j].dest;
    
20.             int weight = graph.edges[j].weight;
    
21.             if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
    
22.                 dist[v] = dist[u] + weight;
    
23.         }
    
24.     }
    
25.      for (int i = 0; i < E; i++) {
    
26.         int u = graph.edges[i].src;
    
27.         int v = graph.edges[i].dest;
    
28.         int weight = graph.edges[i].weight;
    
29.         if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
    
30.             std::cout << "Graph contains negative weight cycle\n";
    
31.             return;
    
32.         }
    
33.     }
    
34.      std::cout << "Vertex\tDistance from Source\n";
    
35.     for (int i = 0; i < V; i++)
    
36.         std::cout << i << "\t" << dist[i] << "\n";
    
37. }
    
38. 
    

复制代码

游客，本帖隐藏的内容需要积分高于 9 才可浏览，您当前积分为 0

3. Java:

1. import java.util.Arrays;
   
2. class Edge {
   
3.     int src, dest, weight;
   
4.      Edge() {
   
5.         src = dest = weight = 0;
   
6.     }
   
7. }
   
8. class Graph {
   
9.     int V, E;
   
10.     Edge[] edges;
    
11.      Graph(int V, int E) {
    
12.         this.V = V;
    
13.         this.E = E;
    
14.         edges = new Edge[E];
    
15.         for (int i = 0; i < E; i++)
    
16.             edges[i] = new Edge();
    
17.     }
    
18. }
    
19. class BellmanFord {
    
20.     void BellmanFord(Graph graph, int src) {
    
21.         int V = graph.V, E = graph.E;
    
22.         int[] dist = new int[V];
    
23.         Arrays.fill(dist, Integer.MAX_VALUE);
    
24.         dist[src] = 0;
    
25.          for (int i = 1; i < V; ++i) {
    
26.             for (int j = 0; j < E; ++j) {
    
27.                 int u = graph.edges[j].src;
    
28.                 int v = graph.edges[j].dest;
    
29.                 int weight = graph.edges[j].weight;
    
30.                 if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
    
31.                     dist[v] = dist[u] + weight;
    
32.             }
    
33.         }
    
34.          for (int j = 0; j < E; ++j) {
    
35.             int u = graph.edges[j].src;
    
36.             int v = graph.edges[j].dest;
    
37.             int weight = graph.edges[j].weight;
    
38.             if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
    
39.                 System.out.println("Graph contains negative weight cycle");
    
40.                 return;
    
41.             }
    
42.         }
    
43.          System.out.println("Vertex\tDistance from Source");
    
44.         for (int i = 0; i < V; ++i)
    
45.             System.out.println(i + "\t" + dist[i]);
    
46.     }
    
47.    
    
48. }

复制代码

游客，本帖隐藏的内容需要积分高于 9 才可浏览，您当前积分为 0

4. Python:

1. class Edge:
   
2.     def __init__(self, src, dest, weight):
   
3.         self.src = src
   
4.         self.dest = dest
   
5.         self.weight = weight
   
6. class Graph:
   
7.     def __init__(self, V, E):
   
8.         self.V = V
   
9.         self.E = E
   
10.         self.edges = []
    
11. def BellmanFord(graph, src):
    
12.     V = graph.V
    
13.     E = graph.E
    
14.     dist = [float('inf')] * V
    
15.     dist[src] = 0
    
16.      for _ in range(V - 1):
    
17.         for i in range(E):
    
18.             u = graph.edges[i].src
    
19.             v = graph.edges[i].dest
    
20.             weight = graph.edges[i].weight
    
21.             if dist[u] != float('inf') and dist[u] + weight < dist[v]:
    
22.                 dist[v] = dist[u] + weight
    
23.      for i in range(E):
    
24.         u = graph.edges[i].src
    
25.         v = graph.edges[i].dest
    
26.         weight = graph.edges[i].weight
    
27.         if dist[u] != float('inf') and dist[u] + weight < dist[v]:
    
28.             print("Graph contains negative weight cycle")
    
29.             return
    
30.      print("Vertex\tDistance from Source")
    
31.     for i in range(V):
    
32.         print(i, "\t", dist[i])
    
33. V = 5  # Number of vertices
    
34. E = 8  # Number of edges
    
35. 
    

复制代码

游客，本帖隐藏的内容需要积分高于 9 才可浏览，您当前积分为 0

这些示例展示了使用不同编程语言实现贝尔曼福特算法的方式。根据您选择的编程语言，使用相应的示例来实现贝尔曼福特算法。


扫码关注微信公众号，免费查看完整算法内容。