- #1
username_unknown
- 2
- 0
Homework Statement
Given connected, directed and weighted (positive weights) graph. Find the shortest cyclic path for each vertex. Cycles have back edges and can also be self loops.
2. The attempt at a solution
I need some clarifications for this problem related to implementation in C.
After depth first search is finished for the first source vertex, we can detect cycles from that source.
Do we need an additional queue or stack to store total weights for each cycle from one source, and return the largest total sum?
After one source is processed (depth first search traversal is finished for the current source), next vertex becomes the source.
How to reset a vector visited (this is a variable-array) for the next depth first search iteration (with the next source)?
Is there an algorithm that finds shortest cyclic path for each vertex directly, without doing modifications to depth first search algorithm?