Search code examples
algorithmgraphpath-finding

Which algorithm works best for this publlic transportation graph?

i have following graph:

enter image description here

As you can see it is a directional graph with circles. The dotted routes are no real stations.

For example this route a -> bigRound would result in following path: a-b-c-d-e-f-g-e-h-d-b-a

Another example route a->h would result in two found paths: a-b-c-d-e-h and a-b-c-d-e-f-g-e-h (including the southRound)

Im struggling to find a fitting algorithm for this kind of graph. Can you make any suggestions?

To clarify: I search a algorithm that gives me all possible paths from a certain start point to a certain end point. In addition to that this graph represents one round trip. Throughout the day there can be more than one. How do i need to change the graph or is there another method.

Thanks in advance.

Solution

  • The algorithm to find all paths is a modified depth first search

    Start by putting the start vertex on top of a stack.
LOOP
IF stack empty, STOP
Take the top vertex of the stack and add it to the visited list and the current path
Add adjacent vertices which aren't in the visited list to the top of the stack.
If the destination has been reached
    Add current path to output
    Backtrack along path to vertex adjacent to vertex on top of stack, marking vertices as unvisited