Dijkstra’s Algorithm: shortest cost path for a general weighted directed graph

Last time we had Prim’s algo for finding the cost of minimum spanning tree….

I think one of the best book for Algorithms is Introduction to Algorithms by Cormen. In PPC’s word’s you’ll never die of hunger if you read this book. and i think he’s very right.

I’ll paste some text from the book. I found the explanation of dijkstra’s algo in this book to be very useful.

Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) for the case in which all edge weights are nonnegative. In this section, therefore, we assume that w(u, v) ≥ 0 for each edge (u, v) E. As we shall see, with a good implementation, the running time of Dijkstra’s algorithm is lower than that of the Bellman-Ford algorithm.

Dijkstra’s algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. The algorithm repeatedly selects the vertex u V – S with the minimum shortest-path estimate, adds u to S, and relaxes all edges leaving u. In the following implementation, we use a min-priority queue Q of vertices, keyed by their d values.

DIJKSTRA(G, w, s)

1 INITIALIZE-SINGLE-SOURCE(G, s)2

S ← Ø

3 Q ← V[G]4

while Q ≠ Ø

5 do u ← EXTRACT-MIN(Q)6

S ← S {u} 7 for each vertex v Adj[u]

8 do RELAX(u, v, w)

Dijkstra’s algorithm relaxes edges as shown in Figure 24.6. Line 1 performs the usual

initialization of d and π values, and line 2 initializes the set S to the empty set. The algorithm maintains the invariant that Q = V – S at the start of each iteration of the while loop of lines 4-8. Line 3 initializes the min-priority queue Q to contain all the vertices in V ; since S = Ø at that time, the invariant is true after line 3. Each time through the while loop of lines 4-8, a vertex u is extracted from Q = V – S and added to set S, thereby maintaining the invariant.(The first time through this loop,

u = s.) Vertex u, therefore, has the smallest shortest-path estimate of any vertex in V – S. Then, lines 7-8 relax each edge (u, v) leaving u, thus updating the estimate d[v] and the predecessor π[v] if the shortest path to v can be improved by going through u. Observe that vertices are never inserted into Q after line 3 and that each vertex is extracted from Q and added to S exactly once, so that the while loop of lines 4-8 iterates exactly |V| times.

Figure 24.6: The execution of Dijkstra’s algorithm. The source s is the leftmost vertex. The shortest-path estimates are shown within the vertices, and shaded edges indicate predecessor values. Black vertices are in the set S, and white vertices are in the min-priority queue Q = V – S. (a) The situation just before the first iteration of the while loop of lines 4-8. The shaded vertex has the minimum d value and is chosen as vertex u in line 5. (b)-(f) The situation after each successive iteration of the while loop. The shaded vertex in each part is chosen as vertex u in line 5 of the next iteration. The d and π values shown in part (f) are the final values.Because Dijkstra’s algorithm always chooses the “lightest” or “closest” vertex in

V – S to add to set S, we say that it uses a greedy strategy. Greedy strategies are presented in detail in  Chapter 16, but you need not have read that chapter to understand Dijkstra’s algorithm.

Greedy strategies do not always yield optimal results in general, but as the following theorem and its corollary show, Dijkstra’s algorithm does indeed compute shortest paths. The key is to show that each time a vertex u is added to set S, we have d[u] = δ(s, u).

The question :

Implement a modified version of Dijkstra’s shortest cost path for a general weighted directed graph with positive edges costs to find the shortest cost paths from a given start node to all other nodes. Print only the path costs.

Submission filename: allnodes.c (Must be submitted by the start of next class)

Input format:

4                //   <number of nodes>

5                //   <number of edges>

1  2  3        //    <node_1,  node_2,  edge_weight>    // edge list

.

.

.

start_node, goal_node (as required)

CODE:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define infy 9999

struct str1 {      // datastructure for min-priority queue.
  int key;
  int node;
};

typedef struct str1 str;

int **adj;        // adjacency matrix.
int *visited;
str *Q;           // min-priority key.
int *key;         // key[v] = dist of v from start node.

int heap_size;

//  SWAP  

void swap(str *array,int p,int q) {
  str temp;

  temp.key        = (array[p]).key;
  temp.node       = (array[p]).node;

  (array[p]).key  = (array[q]).key;
  (array[p]).node = (array[q]).node;

  (array[q]).key  = temp.key;
  (array[q]).node = temp.node;
}

// MIN HEAPIFY

void min_heapify(str *Q,int i) {
  int left, right, smallest;

  left  = 2*i;
  right = 2*i+1;

  if(left > heap_size)
    return;

  if(left <= heap_size) {
    if (Q[left].key < Q[i].key)
      smallest = left;
    else
      smallest = i;
  }

  if(right <= heap_size)
    if (Q[right].key < Q[smallest].key)       smallest = right;         if(smallest != i) {     swap(Q,i,smallest);          min_heapify(Q,smallest);   } } // BUILD MIN HEAP void build_min_heap(str *Q,int n,int length) {   int i;      for(i = length/2;i > 0;i–)
    min_heapify(Q,i);
}

// EXTRACT MIN

str extract_min(str *Q,int n) {
  str min;
  int i;

  if (heap_size < 1) {
    printf(“HEAP_SIZE < 1\n”);     return;   }      min.key  = Q[1].key;   min.node = Q[1].node;      swap(Q,1,heap_size);      heap_size = heap_size – 1;      min_heapify(Q,1);      return min; } // DECREASE KEY void decrease_key(str *Q,int i,int key) {      if(key > Q[i].key)
    return;

  Q[i].key = key;

  while((i > 1) && (Q[i/2].key > Q[i].key)) {
    swap(Q,i,i/2);
    i = i/2;
  }
}

//

void relax(int u, int v) {
  int i;

  if(key[v] > (key[u] + adj[u][v])) {
    key[v] = key[u] + adj[u][v];

    for(i = 1;i <= heap_size;i++) {
      if(Q[i].node == v) {
	decrease_key(Q,i,key[v]);
	break;
      }
    }
  }
}

// MAIN

int main() {

  int n, e, node1, node2, i, j;
  int root, wt, u, v;
  str temp;
  int a, length, start;

  printf(“no of nodes :: “);
  scanf(“%d”,&n);

  adj = (int **)calloc(n+1,sizeof(int *));

  for(i = 1;i <= n;i++)
    adj[i] = (int *)calloc(n+1,sizeof(int));

  for(i = 1;i <= n;i++)
    for(j = 1;j <= n;j++)
      adj[i][j] = infy;

  a = log(n)/log(2);
  length = pow(2,a+1);

  heap_size = n;

  Q = (str *)calloc(length + 1,sizeof(str));

  printf(“no. of edges :: “);
  scanf(“%d”,&e);

  printf(“Enter the edges & weights edge1 edge2 weight.\n”);

  for(i = 1;i <= e;i++) {
    scanf(“%d%d%d”,&node1,&node2,&wt);
    adj[node1][node2] = wt;
  }

  printf(“Starting node :: “);
  scanf(“%d”,&start);

  key     = (int *)calloc(n + 1,sizeof(int));

  visited = (int *)calloc(n + 1,sizeof(int));

  // initialize

  for(i = 0;i <= n;i++)
    key[i]    = infy;

  key[start] = 0;

  // min priority queue Q.

  for(i = 1;i <= n;i++) {
    Q[i].key  = key[i];
    Q[i].node = i;
  }

  build_min_heap(Q,n,length);

  while(heap_size != 0) {
    temp = extract_min(Q,n);
    u = temp.node;

    visited[u] = 1;

    for(v = 1;v <= n;v++) {
      if(adj[u][v] != infy) {
	relax(u,v);
      }
    }
  }

  printf(“The shortest cost paths from %d are \n”,start);

  for(i = 1;i <= n;i++)
    printf(“%d\t%d\n”,i,key[i]);

  printf(“\n”);

  return 0;

}

the algolabphobia…

What is computer science…..???

comp sc is the design and analysis of algorithms.

and with this course comes the algolab.I don’t no about other colleges, but in IIT kgp, this is the most annoying lab.(at least for me).It weighs little in terms of grades coz it has only 2 credits, bt then, it is our bread and butter, so we can’t leave iot unattended.

I’ve learned quiet a lot from this algolab…no I’m not talking about coding experience…Its about something more important…i.e. your attitude towards life…Now one might wonder what is the connection between algolab and attitude…But then to really understand this you’ll have to come to kgp and experience it yourself.

this algolab is in our curricullum in the 2nd year(3rd sem).And the raggigng ( better call it Orientation Programme or the more popular “OP”) period comes in 2nd year…ya ya i know its strange…coz all other colgs hv it in 1st year…its so here because we shift to senior halls in 2nd year…so we have to face the combination of ragging + algolab.and both demand time. The sole purpose of ragging is to ensure that you know all your battchmates and seniors well.and obviously for that you need to spend quiet a lot of time meeting all your batchmates…and seniors …knowing all your “hall fundas”…all this takes a lot of time…so at the end of the day we’re left with little or no time…

In the algolab, we’re given an assignment, we’re supposed to submit the assignment brfore next lab i.e. within a period of one week. So it becomes really very difficult to manage both of them at the same time. In the 1st few weeks you just won’t understand what’s happening. And by the time you realise everything …its too late. The assignments carry marks nd hence reflect in your grade sheet. so you xcan’t just drop it. It demands attention.

i used to spend 90% of my time on monday trying to code the assignment. I knew that internet is an excellent resource. But it dissapointed me. I’ll get the algo everywhere, but no one will give you the code.and even if you get one…it’ll be in java. Our submissions are in C only. So even internet proved to be of no use. So i decided that i’ll put up all my algolab assignments on the net so that if anyone needs the codes in C language he can use it.

BUT THERE’S ONE THING THAT I WOULD LIKE TO SAY.PLEASE DON’T JUST COPY AND PASTE THIS STUFF.BECAUSE THAT WOULD DEFEAT THE SOLE PURPOSE OF HAVING THIS LAB IN THE CURRICULLUM.

You can take ideas from here but do not just copy paste this stuff!!!

I had planned to put this up on net since long but couldn’t do so due to lack of time.So i decided today to atleast write something about it so that i get committed to it.Otherwise like all good ides even this one wud get lost.

ppc

well well before i put up any codes i’d like to talk about Prof. Parth Pratim Chakraborti ( or PPC as he is better known). He;s the busiest person in the institute. He’s also the Dean of SRIC, Sponsored Research and Industrial Consultancy. He’s also our allumni. Its coz of him that i developed such an interest in algorithms. He’s got a unique style of teaching. I’ll talk more about him in the days to come.

But for now i’ll put up one of my favouraite code. The mst.c

Problem :

  1. Write a C Program to implement Prim’s Algorithm for finding the minimum cost spanning tree of a weighted graph. You need to print the cost of the tree and the set of edges of the original graph present in the tree.

The datastrucure used is Heap, because it helps reduce the complexity. The min-priority queue and decrease functions are pretty useful in this context. 

 

Code :

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define infy 9999

struct str1{      // datastructure for min-priority queue.
  int key;
  int node;
};

typedef struct str1 str;

int **adj;        // adjacency matrix.
int *visited;
str *Q;           // min-priority key.
int *key;         // key[v] = min wt. of any
                  // edge joining v to tree.
int *parent;      // stores the parent node.

int heap_size;

//…………..  SWAP  ……………..

void swap(str *array,int p,int q)
{
  str temp;
 
  temp.key        = (array[p]).key;
  temp.node       = (array[p]).node;
 
  (array[p]).key  = (array[q]).key;
  (array[p]).node = (array[q]).node;
 
  (array[q]).key  = temp.key;
  (array[q]).node = temp.node;
}

// ………. MIN HEAPIFY  ……………..

void min_heapify(str *Q,int i)
{
  int left,right,smallest;
 
  left  = 2*i;
  right = 2*i+1;
 
  if(left > heap_size)
    return;
 
  if(left <= heap_size)
    {
      if(Q[left].key < Q[i].key)
 smallest = left;
      else smallest = i;
    }
 
  if(right <= heap_size)
    if(Q[right].key < Q[smallest].key)
      smallest = right;
 
 
  if(smallest != i)
    {
      swap(Q,i,smallest);
     
      min_heapify(Q,smallest);
    }
}

// …………….  BUILD MIN HEAP  ……………..

void build_min_heap(str *Q,int n,int length)
{
  int i;
 
  for(i = length/2;i > 0;i–)
    min_heapify(Q,i);
}

//…………. EXTRACT MIN……………

str extract_min(str *Q,int n)
{
  str min;
  int i;
 
  if (heap_size < 1)
    {
      printf(“HEAP_SIZE < 1\n”);
      return;
    }
 
  min.key  = Q[1].key;
  min.node = Q[1].node;
 
  swap(Q,1,heap_size);
 
  heap_size = heap_size – 1;
 
  min_heapify(Q,1);
 
  return min;
}

//  ………….  DECREASE KEY ………………….

void decrease_key(str *Q,int i,int key)  //decrease the key of elt. i
{
 
  if(key > Q[i].key)
    return;
 
  Q[i].key = key;
 
  while((i > 1) && (Q[i/2].key > Q[i].key))
    {
      swap(Q,i,i/2);
      i = i/2;
    }
}

 

//………………  MAIN  ……………….

 

int main()
{
 
  int n,e,node1,node2,i,j;
  int root,wt,u,v,cost;
  str temp;
  int a,length;
 
 
  printf(“no of nodes :: “);
  scanf(“%d”,&n);
 
  adj = (int **)calloc(n+1,sizeof(int *));
 
  for(i = 1;i <= n;i++)
    adj[i] = (int *)calloc(n+1,sizeof(int));
 
  for(i = 1;i <= n;i++)
    for(j = 1;j <= n;j++)
      adj[i][j] = infy;
 
  a = log(n)/log(2);
  length = pow(2,a+1);
 
  heap_size = n;
 
  Q = (str *)calloc(length + 1,sizeof(str));
 
  printf(“no. of edges :: “);
  scanf(“%d”,&e);
 
  printf(“Enter the edges & weights edge1 edge2 weight.\n”);
 
  for(i = 1;i <= e;i++)
    {
      scanf(“%d%d%d”,&node1,&node2,&wt);
      adj[node1][node2] = wt;
      adj[node2][node1] = wt;
    }
 
  key     = (int *)calloc(n + 1,sizeof(int));
 
  visited = (int *)calloc(n + 1,sizeof(int));
 
   
  // initialize
 
  for(i = 0;i <= n;i++)
    {
      key[i]    = infy;
 
    }
 
  // choosing the root.
 
  root = 1;
 
  key[root] = 0;
 
 
  // min priority queue Q.
 
  for(i = 1;i <= n;i++)
    {
      Q[i].key  = key[i];
      Q[i].node = i;
    }
 
  build_min_heap(Q,n,length);
 
  cost = 0;
 
  while(heap_size != 0)
    {
      temp = extract_min(Q,n);
      u = temp.node;
      cost = cost + temp.key;
      visited[u] = 1;
     
      for(v = 1;v <= n;v++)
 {
   if(adj[u][v] != infy)
     {
       if(visited[v] == 0)
  {
    if(adj[u][v] < key[v])
      {
        key[v] = adj[u][v];
       
        for(i = 1;i <= heap_size;i++)
   {
     if((Q[i]).node == v)
       {
         // decrease the key of node v(contained in
         // elt i of min-priority queue Q) to adj[u][v]
        
         decrease_key(Q,i,adj[u][v]);
         break;
       }
   }
      }
  }
     }
 }
    }
 
 
  printf(“The Cost of shortest spanning tree = %d\n\n”,cost);
 
  printf(“\n\n”);
 
  return 0;
 
}

 

//*************************************