Dijkstra Algorithm

Objective: The objective of this assignment is to give you practice in implementing fairly non-trivial algorithms using efficient data structures.

Your Task:

• For this assignment you need to implement Dijkstras Algorithm for finding Single Source Shortest Paths. You can assume that the input graph is a directed weighted graph. You can also assume that all edge weights are non-negative.
• Use the Adjacency List Representation to store and process the graph. Adjacency List representation is more suitable for this problem than the Adjacency Matrix Representation
• For the priority queue data structure needed by the Dijkstras Algorithm, use the Binary Heap Data Structure. The heap data structure is not explicitly taught in this course. You should have learnt it in an undergraduate Data Structures course equivalent to our CSCI 2530. In case you are not familiar with it, you can read up from the book. The heap data structure is discussed in Section 2.5 of your textbook.
  
  Note that the trees involved in the heap exist only in your mind as a concept and you will actually use an array to implement the heap. Basically, you need three procedures that deal with heap data structures viz., BUILD MIN HEAP, HEAP EXTRACT MIN and HEAP DECREASE KEY. You can build the initial heap either by repeated insertion or by using a HEAPIFY procedure.

• Make sure that the time complexity of your implementation of Dijkstras Algorithm is of the order ((V + E) lg V ). While implementing, it is very easy to code certain segments of the algorithm which are not spelt in full detail in such a way that the complexity of your program becomes more than the specified complexity of the algorithms. Be extra careful to avoid such pitfalls.
• Make sure that your programs are written in C++ and Java and that they can run on the Linux system. Include a README file, if I need to do anything special to compile and run your program. Also, include any additional assumptions you are making and/or ways in which you are deviating from the given specifications in such a README file. Your programs should be reasonably commented as well.

Input Format: Your program should read the input from stdin. The input format will be

n
e
a1 b1 w1
a2 b2 w2
a3 b3 w3
.
.
.
.
ae be we

The number N in the first line specifies the total number of vertices in the graph. You may assume that the vertices are numbered from 1 through N . The number E in the second line specifies the total number of edges in the graph. The remaining lines describe the edges one per line. The interpretation should be that the edge from the vertex A_i to the vertex B_i has weight W_i. The edges may be presented to you in any order and hence do not assume anything about the order of the edges. Also note that the weights need not be integers. You may assume that the edge weights are non-negative. You may assume that the input data given is consistent. You may assume that the vertex with number 1 is the source vertex.

Output Format: Your program should write the output to stdout. You should produce three lines of output for each vertex. Sample output format is shown below.

Vertex 5
Shortest Distance is 23.5
Shortest Path is 1 8 6 3 5

First line specifies the sink vertex number, the second line specifies the shortest distance to the sink from the source and finally the third line specifies a shortest path by listing the sequence of vertices in the path starting from the source to the sink.