In this programming assignment, you are required to implement and test Dijkstra’s algorithm for sparse graphs. Below are
Posted: Mon May 02, 2022 12:01 pm
In this programming assignment, you are required to implement and test Dijkstra’s
algorithm for sparse graphs. Below are some (optional) steps to guide you through this
process.
You are required to add comments to your code for a better readability.
We assume here that the vertices of a graph G are numbered from 0 to n-1.
1- Start by representing a weighted graph G using an adjacency list. For that, you may
need to implement two functions:
o addEdge(): the weight of an edge (u, v) must be added to the entries u and v
in the adjacency list.
o printGraph(): prints the graph G.
2- Use a min-heap to guarantee a running time of O(log n) for the heap operations. Since
the heap must be updatable, each of its elements must contain a node v and its current
known distance dv. In other words, the min-heap should keep track of all the
(unmarked) vertices of G together with their shortest distances known so far.
3- Use the following arrays:
o position: Keeps track of the position of a vertex u in the min-heap. This
array guarantees the fact that updating the position of u can be done in constant
time.
o marked: Boolean array to keep track of the processed nodes.
o parent: Keeps track of previous nodes when building the shortest path from
the source S to a node u.
Once done, test your program in a main function.
Note: Use C++, JAVA or Python to implement Dijkstra’s algorithm.
algorithm for sparse graphs. Below are some (optional) steps to guide you through this
process.
You are required to add comments to your code for a better readability.
We assume here that the vertices of a graph G are numbered from 0 to n-1.
1- Start by representing a weighted graph G using an adjacency list. For that, you may
need to implement two functions:
o addEdge(): the weight of an edge (u, v) must be added to the entries u and v
in the adjacency list.
o printGraph(): prints the graph G.
2- Use a min-heap to guarantee a running time of O(log n) for the heap operations. Since
the heap must be updatable, each of its elements must contain a node v and its current
known distance dv. In other words, the min-heap should keep track of all the
(unmarked) vertices of G together with their shortest distances known so far.
3- Use the following arrays:
o position: Keeps track of the position of a vertex u in the min-heap. This
array guarantees the fact that updating the position of u can be done in constant
time.
o marked: Boolean array to keep track of the processed nodes.
o parent: Keeps track of previous nodes when building the shortest path from
the source S to a node u.
Once done, test your program in a main function.
Note: Use C++, JAVA or Python to implement Dijkstra’s algorithm.