MH3400 Algorithms for the Real World AY 2021/2022
Thomas Peyrin
Lab Session (week 9)
Deadline: 23.03.2022 11:59pm SGT
Complete all assignments below. Once you are done, submit the file(s) via NTU Learn. Remember to put
plenty of comments for all assignments, as this helps us to better understand your program (which might
give you higher marks).
Important!!! Make sure your scripts work properly, as we give 0 marks otherwise. Please
name the scripts according to the requirements, and upload each file separately and not in a
Zip file or similar. The submission system closes at the deadline. Hence after that, you will
get no marks for your solution.
For this lab session, you will have to program the Dijkstra’s algorithm for a directed graph (without
using a priority queue) and the Floyd-Warshall’s algorithm. You can download on NTU Learn the
template file shortest path.py which contains the skeleton of the algorithms you have to implement.
As in the previous lab session on graphs, the graph is stored as an adjacency list, but this time we add the
weight for each edge. For example, we have for the following graph:
g = [
[[1,12], [2,6]],
[ ],
[[3,17]],
[[0,15]]
]
ˆ Your first task is to implement the function dijkstra(G,s) that computes for the graph G the distance
between node s and all the other nodes of G. It will return a distance list accordingly (a list of n
elements). Using the example graph above, it should return:
[0, 12, 6, 23]
ˆ Your second task is to implement the function floyd warshall(G) that computes for the graph G the
distance between all pairs of nodes in G. It will return a 2-dimension list, i.e. a list that contains n
distance lists Li each of n elements and containing the distance table from node i. Using the example
graph above, starting from node 0, it should return:
[
[0, 12, 6, 23],
[inf, 0, inf, inf],
[32, 44, 0, 17],
[15, 27, 21, 0]
]
Note that the input graph is stored as an adjacency list, not as an adjacency matrix. You have to
make sure your implementation runs in O(n3) at maximum and for that you will need the initialisation
part to run in O(n2 + m) (and not the naive O(n2m)).
1