The shortest path to one place in the schedule

Question

For the graph and the destination node, as you will find all the shortest paths from all other vertices to the destination vertex.

Answer 1

Dijkstra's algorithm. You can work backwards as if your destination was your starting peak. This will give you the distance and path to any other node.

* PS: Only one thing to remember. You need to flip the edges before using Dijkstra with your destination as your starting peak for this to work.

Answer 2

Assuming this is bi-directional, you can simply start from your destination and work your way out. This is commonly known as the first Breadth Search (BFS).

Everything connected with dest has a distance of 1. Everything connected with any of these nodes (which have not yet been calculated) has a distance of 2. Repeat until you exit the nodes.

Even if it was not bidirectional, you could still do it quite easily by pretending to be your bidirectional movement in one pass through the nodes to start with.

In any case, to do this, you need to arrange (V + E), where V is your number of nodes, and E is your number of edges.

Answer 3

The Dijkstra algorithm is good if you have weighted edges and you want to minimize the total cost of weights on the way, but in an unweighted graph (all faces have the same cost), a simple width search will do the trick.

Answer 4

Just to fulfill the most useful answer above.

For this solution to work, you need to rotate the edges of the graph before using Dijkstra with your destination as the starting vertex.