1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: C data structures and algorithms - graph problem

  1. Jul 27, 2016 #1
    1. The problem statement, all variables and given/known data
    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?
  2. jcsd
  3. Jul 28, 2016 #2


    User Avatar
    2017 Award

    Staff: Mentor

    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?
    You can start the whole algorithm from scratch again. This is not necessarily the optimal approach but it works.
  4. Jul 28, 2016 #3


    User Avatar
    Science Advisor
    Gold Member

    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
    Code (Text):
    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(V3), 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.
    Last edited: Jul 28, 2016
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted