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