C data structures and algorithms - graph problem

[username_unknown]

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?

 

[mfb]

Do we need an additional queue or stack to store total weights for each cycle from one source, and return the largest total sum?

What do you mean by "each cycle"? Do you have more than one? Where and why would you want to have the largest total sum of anything?

How to reset a vector visited (this is a variable-array) for the next depth first search iteration (with the next source)?

You can start the whole algorithm from scratch again. This is not necessarily the optimal approach but it works.

 

[QuantumQuest]

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?

I think that utilizing DFS in this case, may lead to exponential times.

You can use Floyd - Warshall algorithm https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm or Dijkstra's algorithm https://en.wikipedia.org/wiki/Dijkstra's_algorithm, for shortest (even cyclic paths), but you inevitably have to modify whichever you choose. One such modification is setting

path[i][i] = infinity

. You must also keep track of where the algorithm finds cycle, in order to find which nodes lead to cycles. Keep in mind that whichever one of the two algorithms you use, the complexity will be O(V³), with V denoting the number of nodes.

For the implementation, you have to choose whichever data structure does your job efficiently. Due to the modifications required, you have to think about it.