fork download
copy 
  1. /*
  2.  * Bellman-Ford Algorithm
  3.  *
  4.  * Authored by,
  5.  * Vamsi Sangam
  6.  */
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <limits.h>
  11.  
  12. int GLOBAL = 0;
  13. // This is used to construct
  14. // the Adjacency List
  15. struct node {
  16.     int vertex, weight;
  17.     struct node * next;
  18. };
  19.  
  20. // This is used to construct the Shortest Paths to all
  21. // vertices, as we cannot return multiple values,
  22. // we use a struct
  23. struct pathInfo {
  24.     int vertex, distance, parent;
  25. };
  26.  
  27. // Adds a new edge into the Adjacency List
  28. // Follows Head Insertion for O(1) Insertion
  29. struct node * add(struct node * head, int vertex, int weight)
  30. {
  31.     struct node * p = (struct node *) malloc(sizeof(struct node));
  32.  
  33.     p->vertex = vertex;
  34.     p->weight = weight;
  35.     p->next = head;
  36.  
  37.     return p;
  38. }
  39.  
  40.  
  41. void PrintNegativeCycle(struct pathInfo shortestDistances[], int vertex, int startVertex)
  42. {
  43. 	if (vertex == startVertex) {
  44. 		printf("%d ", vertex);
  45. 		return;
  46. 	} else {
  47. 		PrintNegativeCycle(shortestDistances, shortestDistances[vertex].parent, startVertex);
  48. 		printf("%d ", vertex);
  49. 	}
  50. }
  51.  
  52.  
  53. // Bellman-Ford Algorithm which takes the Graph (adjacencyList[]), starting vertex (startVertex),
  54. // and an empty array shortestDistances[] as input. It applies the algorithm and keeps filling values
  55. // into shortestDistances[]. It returns true if there are no negative edges, and vice-versa.
  56. int bellmanFord(struct node * adjacencyList[], int vertices, int startVertex, struct pathInfo shortestDistances[])
  57. {
  58.     struct node * traverse;
  59.     int i, j, k;
  60.  
  61.     // Initialisation
  62.     for (i = 0; i <= vertices; ++i) {
  63.         shortestDistances[i].vertex = i;
  64.         shortestDistances[i].distance = INT_MAX;
  65.         shortestDistances[i].parent = -1;
  66.     }
  67.  
  68.     // Setting distance to source = 0
  69.     shortestDistances[startVertex].parent = 0;
  70.     shortestDistances[startVertex].distance = 0;
  71.  
  72.     // The Algorithm that computes Shortest Distances
  73.     for (i = 1; i <= vertices - 1; ++i) {        // Runs 'vertices - 1' times = O(|V|)
  74.         for (j = 1; j <= vertices; ++j) {        // Runs as many times as the edges = O(|E|)
  75.             // The code ahead basically explores the whole of Adjcency List,
  76.             // covering one edge once, so the runtime of the code in this
  77.             // block is O(|E|)
  78.  
  79.             traverse = adjacencyList[j];
  80.  
  81.             while (traverse != NULL) {
  82.                 if (shortestDistances[j].distance == INT_MAX) {
  83.                     // Important...!
  84.                     traverse = traverse->next;
  85.                     continue;
  86.                 }
  87.  
  88.                 // Checking for Relaxation
  89.                 if (traverse->weight + shortestDistances[j].distance < shortestDistances[traverse->vertex].distance) {
  90.                     // Relaxation
  91.                     shortestDistances[traverse->vertex].distance = traverse->weight + shortestDistances[j].distance;
  92.                     shortestDistances[traverse->vertex].parent = j;
  93.                 }
  94.  
  95.                 traverse = traverse->next;
  96.             }
  97.         }
  98.     }
  99.  
  100.     // Checking for Negative Cycles
  101.     for (j = 1; j <= vertices; ++j) {
  102.         traverse = adjacencyList[j];
  103.  
  104.         while (traverse != NULL) {
  105.             // Checking for further relaxation
  106.             if (traverse->weight + shortestDistances[j].distance < shortestDistances[traverse->vertex].distance) {
  107. 				GLOBAL = j;
  108.                 // Negative Cycle found as further realxation is possible
  109.                 return 0;
  110.             }
  111.  
  112.             traverse = traverse->next;
  113.         }
  114.     }
  115.  
  116.     return 1;
  117. }
  118.  
  119. int main()
  120. {
  121.         int vertices, edges,source, i, j, v1, v2, weight;
  122.  
  123.     printf("Enter the Number of Vertices -\n");
  124.     scanf("%d", &vertices);
  125.  
  126.     printf("Enter the Number of Edges -\n");
  127.     scanf("%d", &edges);
  128.  
  129. 	printf("Enter the source Vertex -\n");
  130.     scanf("%d", &source);
  131.     struct node * adjacency_list[vertices + 1];
  132.     //Size is made (vertices + 1) to use the
  133.     //array as 1-indexed, for simplicity
  134.  
  135.     //Must initialize your array
  136.     for (i = 0; i <= vertices; ++i) {
  137.         adjacency_list[i] = NULL;
  138.     }
  139.     printf("Enter the edges -\n");
  140.  
  141.     for (i = 1; i <= edges; ++i) {
  142.         scanf("%d%d%d", &v1, &v2, &weight);
  143.         adjacency_list[v1] = add(adjacency_list[v1], v2, weight);
  144.     }
  145.     //Printing Adjacency List
  146.     printf("\nAdjacency List -\n\n");
  147.     for (i = 1; i <= vertices; ++i) {
  148.         printf("adjacency_list[%d] -> ", i);
  149.  
  150.         struct node * temp = adjacency_list[i];
  151.  
  152.         while (temp != NULL) {
  153.             printf("(%d, %d) -> ", temp->vertex, temp->weight);
  154.             temp = temp->next;
  155.         }
  156.  
  157.         printf("NULL\n");
  158.     }
  159.  
  160.     struct pathInfo shortestDistances[vertices + 1];
  161.     int startVertex;
  162.  	startVertex = source;
  163.  	int check = bellmanFord(adjacency_list, vertices, startVertex, shortestDistances);
  164.     if (check == 1) {
  165.         printf("No Negative Cycles exist in the Graph -\n");
  166.     } else {
  167.         printf("Negative Cycles exists in the Graph -\n");
  168.  
  169. 		printf("GLOBAL VARIABLE: %d\n",GLOBAL);
  170. 		printf("Vertices in negatice Cycle: ");
  171. 		PrintNegativeCycle(shortestDistances, shortestDistances[GLOBAL].parent, GLOBAL);
  172.  
  173. 		printf("\n");
  174.         return 0;
  175.     }
  176.  
  177.     printf("\n\nVertex    Shortest Distance to Vertex %d     Parent Vertex-\n", startVertex);
  178.     for (i = 1; i <= vertices; ++i) {
  179.         printf("%d         %d                                 %d\n", i, shortestDistances[i].distance, shortestDistances[i].parent);
  180.     }
  181.  
  182.     return 0;
  183. }
Runtime error #stdin #stdout 0s 2188KB
comments (?)
stdin
copy 
3 3
3
2 1 -10
3 2 -10
1 3 -10
stdout
copy 
Standard output is empty
https://ideone.com/kGZUKe
language:
C (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!