C# with the correct Output

Due on 11/17/2014  13:00PM

 

Task: Implement Dijkstra’s algorithm.

1. Number the vertices from 1 to n (Suppose G has n vertices) 

2. Adjacent lists G: (i) define an array Adj of n nodes, where Adj[i] leads a linked list that saves the neighbors of vertex i. (ii) Each node in linked list Adj[i] contains (a) a neighbor (say j) of i, (b) the weight that i with the neighbor (say w(i,j)) and (c) the link to the next node.

3. Priority queue Q: there are n items (one item for each vertex) in Q, where the item for vertex i contains p[i] and d[i], and d[i] is used as key for Q.

4. Structure of the implementation

method: dijkstra(G, w, s) which return p

main method:

main()

{   input the graph in Input:

Graph G=(V,E)

Weight w(u,v) for each edge (u,v)

Adjacent list Adj[v] for each vertex v  

: create adjacent lists of G, assign value to w, assign value to s;

    call Dijkstra(G,w,s);

    print path of s to each vertex using p;

 }

Requirements

•           A priority queue Q is used for the unprocessed vertices

•           Analyze the time complexity of your implementation using O-notation. Note that the time

   complexity also depends on the data structures you used in the implementation.

•       Use C# for implementation

Grading : 150 Points implemented by min-heap

Submission 

Project description, Algorithm, Algorithm analysis, Description of your implementation including the data structures you use. Experiment output. Code. The output Correctly.