search

Psyf / DataStructsAndAlgos-2040C

Sorting Algorithms taught int 2040C implemented
3 stars 4 forks source link

cs2010_AY1516S1_final.txt #8

Open 0WN463 opened 6 years ago

0WN463 commented 6 years ago

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

  1. 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 commented 6 years ago

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.