COMP 3270 Introduction to Algorithms
Homework 4
Adjacency Matrix
Represent the follow graph using its adjacency matrix. The number in the circle indicates the
corresponding index of the node. all edge weights are 1.
Note that the graph is directed, i.e., the edges only goes from its source node to its target node but
not backwards.
Prim's Algorithm / MST
Rule out the MST of the following graph using Prims algorithm. The number in the circle indicates
the corresponding index of the node, while the numbers on the edges are their weights,
Use node 0 as the starting node. You must show your work.
Bellman-Ford Algorithm
Consider the following graph
Run Bellman-Ford algorithm on the graph, using vertex a as the source. In each pass,
relax the edges in the order (a, b), (a, c), (d, b), (c, d), (b, e), (e, d).
You must show your work to earn credits.
a b
c d
e
‐4
2
1
5
3
‐3
