CODEWITHSUNDEEP
algorithmgraph-algorithmweighted-graph
erans
erans

Reputation: 13

most lightweight circle in directed graph that goes through specific vertex

I have directed Graph G(V,E) with weight function w. so that weight of each (u,v) is a positive value. I need to find the most lightweight circle in the graph that vertex k' is part of it.

I've also given an algorithm i can use which can find the most lightweight path for a graph with positives weights ( i can use it only once).

I thought about creating a sub graph G' where all vertices and edges that are strongly connected components. find the graph which k' is part of it. then find for the most lightweight adjacent edge from k' to some v of vertices. from that v i can run the algorithm given and find the lightweight path then add the weight of the vertex missing ( (k',v) ).

is that seems correct ? I'm in the beginning of this course and I feel i'm not there yet.

Upvotes: 0

Views: 548

Answers (3)

CMPS
CMPS

Reputation: 7769

Very interesting problem. I am assuming that there are no negative values in the graph, or otherwise the following solutions requires first normalizing the vertices such that the negative values become at least 0. First method (trivial) is to detect all cycles starting from the target vertex (k). Then compute the weight of all those cycles and take the minimum. The second method is to run Dijkstra algorithm (again watch out negative weights) from the target node (k). Then iterate over all incoming edges of (k), and select the source node that has the minimum Dijkstra value. Now the lightest cycle includes the single path (formed by Dijkstra traversal) from (k) to the chosen node + the bridge to come back to (k). I hope that helps :)

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59263

I can't imagine why you called your source vertex k'. Anyway...

Add a new vetrex w that has the same outgoing edges as k'.

Then use Dijkstra's algorithm to find the shortest path from w to k'.

Substitute k' for w in the path, and you have the smallest cycle including k'.

Upvotes: 0

Patrick the Cat
Patrick the Cat

Reputation: 2158

It is a single-source shortest-path problem, where you exclude k->k self-loop as a solution, and find a longer path from k to k. The trick is always expand the shortest path thread.

Given this definition, you can start Googling...

Upvotes: 1

Related Questions