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;

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s