fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #define MAX_NODES 1024
  4. #define INFINITY 1000
  5.  
  6. // Hardcoded graph and its size
  7. int n = 8;
  8. int cost = 0;
  9. int dist[8][8] = {{0, 2, 0, 0, 0, 0, 6, 0},
  10.                   {2, 0, 7, 0, 2, 0, 0, 0},
  11.                   {0, 7, 0, 3, 0, 3, 0, 0},
  12.                   {0, 0, 3, 0, 0, 0, 0, 2},
  13.                   {0, 2, 0, 0, 0, 2, 1, 0},
  14.                   {0, 0, 3, 0, 2, 0, 0, 2},
  15.                   {6, 0, 0, 0, 1, 0, 0, 4},
  16.                   {0, 0, 0, 2, 0, 2, 4, 0}};
  17.  
  18. // Structure to hold state of each node during Dijkstra's algorithm
  19. struct state {
  20.     int pre;
  21.     int length;
  22.     int label;
  23. };
  24.  
  25. // Function to find the shortest distance from source to destination
  26. // using Dijkstra's algorithm.
  27. // s: source vertex, t: destination vertex, path[]: array to store the path
  28. int shortest_dist(int s, int t, int path[]) {
  29.     int i, k, min;
  30.     struct state state[MAX_NODES];
  31.  
  32.     // 1. Initialization
  33.     for (i = 0; i < n; i++) {
  34.         state[i].pre = -1;
  35.         state[i].length = INFINITY;
  36.         state[i].label = 0;
  37.     }
  38.     state[s].length = 0;
  39.  
  40.     // 2. Main loop of Dijkstra's algorithm
  41.     do {
  42.         // Find the unvisited node with the minimum length
  43.         k = -1;
  44.         min = INFINITY;
  45.         for (i = 0; i < n; i++) {
  46.             if (state[i].label == 0 && state[i].length < min) {
  47.                 min = state[i].length;
  48.                 k = i;
  49.             }
  50.         }
  51.  
  52.         // Break if no reachable unvisited nodes are found
  53.         if (k == -1) {
  54.             cost = INFINITY; // No path exists
  55.             return 0;
  56.         }
  57.  
  58.         // Mark the found node as visited/finalized
  59.         state[k].label = 1;
  60.  
  61.         // Update the lengths of its neighbors
  62.         for (i = 0; i < n; i++) {
  63.             if (dist[k][i] != 0 && state[i].label == 0) {
  64.                 if (state[k].length + dist[k][i] < state[i].length) {
  65.                     state[i].pre = k;
  66.                     state[i].length = state[k].length + dist[k][i];
  67.                 }
  68.             }
  69.         }
  70.     } while (state[t].label == 0); // Continue until the destination is finalized
  71.  
  72.     // 3. Path reconstruction and cost calculation
  73.     int path_length = 0;
  74.     int current = t;
  75.  
  76.     // The cost is the final length of the path to the destination node
  77.     cost = state[t].length;
  78.  
  79.     // Reconstruct the path from destination to source using the 'pre' array
  80.     while (current != -1) {
  81.         path[path_length++] = current;
  82.         current = state[current].pre;
  83.     }
  84.  
  85.     return path_length;
  86. }
  87.  
  88. int main() {
  89.     int i, path_len, p, q;
  90.     int path[MAX_NODES];
  91.  
  92.     printf("\nNote: This program uses a hardcoded 8-node graph.\n");
  93.  
  94.     printf("\nEnter Source Vertex (1-8): ");
  95.     scanf("%d", &p);
  96.     printf("\nEnter Destination Vertex (1-8): ");
  97.     scanf("%d", &q);
  98.  
  99.     // Call the function with corrected arguments (source, destination)
  100.     path_len = shortest_dist(p - 1, q - 1, path);
  101.  
  102.     // Check if a path was found
  103.     if (cost == INFINITY) {
  104.         printf("\nNo path exists from vertex %d to vertex %d.\n", p, q);
  105.     } else {
  106.         // Print the path in the correct order (from source to destination)
  107.         printf("\nShortest path: ");
  108.         for (i = path_len - 1; i >= 0; i--) {
  109.             printf("%c", path[i] + 'A');
  110.             if (i > 0) {
  111.                 printf(" -> ");
  112.             }
  113.         }
  114.         printf("\nCost is: %d \n", cost);
  115.     }
  116.  
  117.     return 0;
  118. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Note: This program uses a hardcoded 8-node graph.

Enter Source Vertex (1-8): 
Enter Destination Vertex (1-8): 
No path exists from vertex 5 to vertex 0.
https://ideone.com/MAlNsn
language:
C (gcc 8.3)
created:
1 day 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!