cs2010_AY1516S1_final.txt

[0WN463]

I J K 5 4
H O L 6 3
G N M 7 2
F C B 8 1
E D A 9 0

longest path d) 16
Shouldn't it be 25? There's a snaking alphabetical sequence in there

4. False. Find a cycle using DFS and then see if the edges traversed between them are negative. Reconstructing the path is a bit tricky, but possible
   But DFS will only yield you the first cycle you find. The negative cycle may not be the first cycle.
   And I don't think there's an easy way to modify DFS to let it find all cycles in a graph

C.3
Store the weights of all the edges and sort it in ascending order.
Beginning from the first, do C.2
As soon as you can reach k from 1, that is your answer.
Note: you can speed up this process by using Binary search.

Hmm can you run 1 pass BMF instead? Change the relaxation condition from distance from source to distance of the edge.

[Psyf]

You're right about the first one.
C.3 Im not so sure. My current solution is O(V^2LogV) so that would definitely be an improvement.