0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Just add a node k1 to your graph, that has exactly the same connections as k, with the same weights (you can keep only the edges going to k1 if you'd like), and query the shortest path from k to k1 in your (slightly) extended graph. Your cycle is exactly this path, only replacing back k1 with k at the end of the path.

Your algorithm would be slower and would not always give the right answer: even if v is the closest node to k, maybe it is not in the best cycle (you could for instance have k->v cost 1, v->k cost 100, and k->u and u->k both cost 2 or some u).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.