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