159.201 Algorithms & Data Structures
Assignment 6
Write a C++ program that reads a simple (no loops or parallel edges) edge-weighted directed
graph G = (V, E) from standard input, and computes the distance from node zero to all other
nodes. Your code must run in O(n · log n) with n = |V | + |E|. This can be achieved by using
adjacency lists to represent the graph, and by computing distances using Dijkstra’s algorithm
with a heap to identify the next node (with minimum distance) to process.
Input graphs are given in the format
n m
v1 w1 l1
v2 w2 l2
.
.
.
vm wm lm
Here n ≥ 1 and m ≥ 0 denote the number of nodes and edges in the graph, and each of the
following line describes an edge from vi to wi of length li
. All nodes vi
, wi
lie in [0 . . . n), and
li
is a positive integer between 1 and 99. There can be nodes that are unreachable from node
zero. For all other nodes, it is guaranteed that the distance from zero will not exceed 106
.
Your program should print the distances from node zero to all other nodes in ascending order,
separated by a single space. When a node is unreachable, print inf instead. For example:
0 1 2
3 4 5
4
2
99
2
1 3 1 3
Input Output
6 8 0 3 8 2 inf 5
0 1 4
0 3 2
1 2 99
1 5 2
2 5 1
3 1 1
4 1 3
5 2 3
You can use CodeRunner to test your work, but must submit your assignment as usual. If
teamwork is permitted and you work in a team, you must include the names and student IDs
of all team members as comments in your submission, and each team member must submit the
same assignment separately.