fork download
copy 
  1. #include <stdio.h>
  2. #include <limits.h>
  3. #include <stdbool.h>
  4.  
  5. #define V 5
  6.  
  7. int minDistance(int dist[], bool sptSet[]) {
  8.     int min = INT_MAX, min_index = -1;
  9.     for (int v = 0; v < V; v++) {
  10.         if (sptSet[v] == false && dist[v] <= min) {
  11.             min = dist[v];
  12.             min_index = v;
  13.         }
  14.     }
  15.     return min_index;
  16. }
  17.  
  18. void printSolution(int dist[]) {
  19.     printf("Vertex \t Distance from Source\n");
  20.     for (int i = 0; i < V; i++) {
  21.         printf("%d \t %d\n", i, dist[i]);
  22.     }
  23. }
  24.  
  25. void dijkstra(int graph[V][V], int src) {
  26.     int dist[V];
  27.     bool sptSet[V];
  28.  
  29.     for (int i = 0; i < V; i++) {
  30.         dist[i] = INT_MAX;
  31.         sptSet[i] = false;
  32.     }
  33.  
  34.     dist[src] = 0;
  35.  
  36.     for (int count = 0; count < V - 1; count++) {
  37.         int u = minDistance(dist, sptSet);
  38.         if (u == -1) break;
  39.         sptSet[u] = true;
  40.  
  41.         for (int v = 0; v < V; v++) {
  42.             if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
  43.                 && dist[u] + graph[u][v] < dist[v]) {
  44.                 dist[v] = dist[u] + graph[u][v];
  45.             }
  46.         }
  47.     }
  48.  
  49.     printSolution(dist);
  50. }
  51.  
  52. int main() {
  53.     int graph[V][V] = {
  54.         {0, 4, 0, 0, 0},
  55.         {4, 0, 8, 0, 0},
  56.         {0, 8, 0, 7, 0},
  57.         {0, 0, 7, 0, 9},
  58.         {0, 0, 0, 9, 0}
  59.     };
  60.  
  61.     printf("Dijkstra Algorithm - Shortest Path\n");
  62.     printf("Graph: 0--4--1--8--2--7--3--9--4\n\n");
  63.     printf("Shortest distances from vertex 0:\n");
  64.  
  65.     dijkstra(graph, 0);
  66.  
  67.     return 0;
  68. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Dijkstra Algorithm - Shortest Path
Graph: 0--4--1--8--2--7--3--9--4

Shortest distances from vertex 0:
Vertex 	 Distance from Source
0 	 0
1 	 4
2 	 12
3 	 19
4 	 28
https://ideone.com/UnIVDQ
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!