# C++ Program to Find the Shortest Path using Bellman Ford Algorithm

«
»
This is a C++ Program to find the shortest path algorithm using Bellman-Ford algorithm. This algorithm also entertains negative edge weights.

Here is source code of the C++ Program to Use the Bellman-Ford Algorithm to Find the Shortest Path Between Two Vertices Assuming that Negative Size Edges Exist in the Graph. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include <stdio.h>`
2. `#include <stdlib.h>`
3. `#include <string.h>`
4. `#include <limits.h>`
5. ` `
6. `// a structure to represent a weighted edge in graph`
7. `struct Edge`
8. `{`
9. `        int src, dest, weight;`
10. `};`
11. ` `
12. `// a structure to represent a connected, directed and weighted graph`
13. `struct Graph`
14. `{`
15. `        // V-> Number of vertices, E-> Number of edges`
16. `        int V, E;`
17. ` `
18. `        // graph is represented as an array of edges.`
19. `        struct Edge* edge;`
20. `};`
21. ` `
22. `// Creates a graph with V vertices and E edges`
23. `struct Graph* createGraph(int V, int E)`
24. `{`
25. `    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));`
26. `    graph->V = V;`
27. `    graph->E = E;`
28. ` `
29. `    graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));`
30. ` `
31. `    return graph;`
32. `}`
33. ` `
34. `// A utility function used to print the solution`
35. `void printArr(int dist[], int n)`
36. `{`
37. `    printf("Vertex   Distance from Source\n");`
38. `    for (int i = 0; i < n; ++i)`
39. `        printf("%d \t\t %d\n", i, dist[i]);`
40. `}`
41. ` `
42. `// The main function that finds shortest distances from src to all other`
43. `// vertices using Bellman-Ford algorithm.  The function also detects negative`
44. `// weight cycle`
45. `void BellmanFord(struct Graph* graph, int src)`
46. `{`
47. `    int V = graph->V;`
48. `    int E = graph->E;`
49. `    int dist[V];`
50. ` `
51. `    // Step 1: Initialize distances from src to all other vertices as INFINITE`
52. `    for (int i = 0; i < V; i++)`
53. `        dist[i] = INT_MAX;`
54. `    dist[src] = 0;`
55. ` `
56. `    // Step 2: Relax all edges |V| - 1 times. A simple shortest path from src`
57. `    // to any other vertex can have at-most |V| - 1 edges`
58. `    for (int i = 1; i <= V - 1; i++)`
59. `    {`
60. `        for (int j = 0; j < E; j++)`
61. `        {`
62. `            int u = graph->edge[j].src;`
63. `            int v = graph->edge[j].dest;`
64. `            int weight = graph->edge[j].weight;`
65. `            if (dist[u] != INT_MAX && dist[u] + weight < dist[v])`
66. `                dist[v] = dist[u] + weight;`
67. `        }`
68. `    }`
69. ` `
70. `    // Step 3: check for negative-weight cycles.  The above step guarantees`
71. `    // shortest distances if graph doesn't contain negative weight cycle.`
72. `    // If we get a shorter path, then there is a cycle.`
73. `    for (int i = 0; i < E; i++)`
74. `    {`
75. `        int u = graph->edge[i].src;`
76. `        int v = graph->edge[i].dest;`
77. `        int weight = graph->edge[i].weight;`
78. `        if (dist[u] != INT_MAX && dist[u] + weight < dist[v])`
79. `            printf("Graph contains negative weight cycle");`
80. `    }`
81. ` `
82. `    printArr(dist, V);`
83. ` `
84. `    return;`
85. `}`
86. ` `
87. `// Driver program to test above functions`
88. `int main()`
89. `{`
90. `    /* Let us create the graph given in above example */`
91. `    int V = 5; // Number of vertices in graph`
92. `    int E = 8; // Number of edges in graph`
93. `    struct Graph* graph = createGraph(V, E);`
94. ` `
95. `    // add edge 0-1 (or A-B in above figure)`
96. `    graph->edge.src = 0;`
97. `    graph->edge.dest = 1;`
98. `    graph->edge.weight = -1;`
99. ` `
100. `    // add edge 0-2 (or A-C in above figure)`
101. `    graph->edge.src = 0;`
102. `    graph->edge.dest = 2;`
103. `    graph->edge.weight = 4;`
104. ` `
105. `    // add edge 1-2 (or B-C in above figure)`
106. `    graph->edge.src = 1;`
107. `    graph->edge.dest = 2;`
108. `    graph->edge.weight = 3;`
109. ` `
110. `    // add edge 1-3 (or B-D in above figure)`
111. `    graph->edge.src = 1;`
112. `    graph->edge.dest = 3;`
113. `    graph->edge.weight = 2;`
114. ` `
115. `    // add edge 1-4 (or A-E in above figure)`
116. `    graph->edge.src = 1;`
117. `    graph->edge.dest = 4;`
118. `    graph->edge.weight = 2;`
119. ` `
120. `    // add edge 3-2 (or D-C in above figure)`
121. `    graph->edge.src = 3;`
122. `    graph->edge.dest = 2;`
123. `    graph->edge.weight = 5;`
124. ` `
125. `    // add edge 3-1 (or D-B in above figure)`
126. `    graph->edge.src = 3;`
127. `    graph->edge.dest = 1;`
128. `    graph->edge.weight = 1;`
129. ` `
130. `    // add edge 4-3 (or E-D in above figure)`
131. `    graph->edge.src = 4;`
132. `    graph->edge.dest = 3;`
133. `    graph->edge.weight = -3;`
134. ` `
135. `    BellmanFord(graph, 0);`
136. ` `
137. `    return 0;`
138. `}`

Output:

```\$ g++ BellmanFord.cpp
\$ a.out

Vertex   Distance from Source
0 		 0
1 		 -1
2 		 2
3 		 -2
4 		 1

------------------
(program exited with code: 0)

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now! 