Dijshtras Algorithm

// Dijsktra's Algorithm
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define   V   9
#define true  1
#define false 0

void dijkstra(int A[V][V], int src);
int minDistance(int dist[], int ShortestPathSet[]);
int printSolution(int dist[V], int src);

int main()
{
     int graph[V][V] = {{0,  4, 0,  0,  0,  0, 0,  8, 0},
                        {4,  0, 8,  0,  0,  0, 0, 11, 0},
                        {0,  8, 0,  7,  0,  4, 0,  0, 2},
                        {0,  0, 7,  0,  9, 14, 0,  0, 0},
                        {0,  0, 0,  9,  0, 10, 0,  0, 0},
                        {0,  0, 4,  0, 10,  0, 2,  0, 0},
                        {0,  0, 0, 14,  0,  2, 0,  1, 6},
                        {8, 11, 0,  0,  0,  0, 1,  0, 7},
                        {0,  0, 2,  0,  0,  0, 6,  7, 0}
                       };
     
     dijkstra(graph,0);
                       
     return 0;
}

void dijkstra(int graph[V][V], int src)
{
    int i,v,u,count;
    int dist[V]; // Output array - dist[i] holds shortest distance
                 // from src to i.
                
    int ShortestPathSet[V]; // ShortestPathSet[i] will hold true if 
                            // shortest distance from src to i is final.
                            
    // Initialize all distances as infinitu and ShortestPathSet as FALSE
    for(i=0; i < V; i++)
    {
       dist[i]            = INT_MAX;
       ShortestPathSet[i] = false;
    }
    
    // Distance from src vertex to itself is always '0'
    dist[src] = 0;
    
    // Find shortest path for all vertices
    for(count = 0; count < V-1; count++)
    {
        // Pick the minimum distance vertex from the set of vertices not
        // yet processed. u is always equal to src in first iteration.
        u = minDistance(dist,ShortestPathSet);
        
        // Mark the picked vertex as finalized
        ShortestPathSet[u] = true;
        
        // Update dist value of the adjacent vertices of the picked vertex
        for(v=0; v < V; v++)
        {
           // Update dist[v] value only if ShortestPathSet[v] is false.
           // Update dist[v] value only if there is an edge from 'u' to 'v',
           //                      and total weight of path from src to 'v'
           //                      through 'u' is smaller than current dist[v].
           if(!ShortestPathSet[v] && graph[u][v])
           {
              if(dist[u] != INT_MAX && // Just a sanity check
                 dist[u]+graph[u][v] < dist[v])
              {
                  dist[v] = dist[u] + graph[u][v];
              }
           }
        }
    }
    
    // Print the constructed distance array
    printSolution(dist, src);
}

int minDistance(int dist[], int ShortestPathSet[])
{
   int i;
   int min = INT_MAX;
   int min_index;
   
   for (i = 0; i < V; i++)
   {
      if(ShortestPathSet[i] == false && dist[i] <= min)
      {
           min       = dist[i];
           min_index = i;
      }
   }
   
   return min_index;
}

int printSolution(int dist[V], int src)
{
  int i;
  
  printf("Distances from Source at index %d to each vertex:\n\n", src);  
  printf("Vertex   Distance from Source\n");
  for(i=0; i<V; i++)
  {
     printf("%d \t \t %d\n",i,dist[i]);
  }
}