### Halym2007's blog

By Halym2007, history, 3 months ago,

• -5

 » 3 months ago, # |   +3 Dijkstra Algorithm for Each VertexRun Dijkstra from each vertex. While doing so, keep track of the shortest path to each other vertex.When considering a new edge during the algorithm, if the edge leads to a vertex already visited, you have found a cycle. Calculate its length and compare it with the shortest cycle found so far.
•  » » 3 months ago, # ^ |   0 what is your time complexity?
•  » » » 3 months ago, # ^ |   +8 $O(EV\log V)$
•  » » » » 3 months ago, # ^ |   0 Is there any way to find with MST(minimum spanning tree)?
•  » » » » » 3 months ago, # ^ |   +1 Are you looking for something faster than $O(EV)$? If yes, that isn't possible with MST. Consider a graph where every edge has the same weight. Now the MST is just any spanning tree and it doesn't give you any extra info. This case can be solved in $O(EV)$ by replacing dijkstra with bfs since all edges have the same weight, but nothing faster is possible afaik.
•  » » » » » » 3 months ago, # ^ |   0 thanks
•  » » 3 months ago, # ^ |   0 thanks
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 You can also do this in O(V^3) using Floyd
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Is there a less-than-O(V^3) approach, though?
 » 3 months ago, # |   0 Given a positive weighted undirected graph, find the minimum weight cycle in it. The idea is to use shortest path algorithm. We one by one remove every edge from the graph, then we find the shortest path between two corner vertices of it. We add an edge back before we process the next edge.Halym2007
•  » » 3 months ago, # ^ |   0 What is your time complexity ?