This page presents several corrected exercises on the problem of shortest way. The exercises focus on the shortest path to one source and the shortest path from multiple sources.
Exercise 1
| TO | B | VS | D | E | |
| TO | 1h30 | 2h00 | 2h15 | ||
| B | 1h40 | 3h00 | |||
| VS | 2h20 | 2h55 | |||
| D | 3h20 | 1h05 | |||
| E | 2h25 | 3h10 | 1h10 |
Just draw the graph, the vertices of which are the cities and the arcs the routes of the company, valued at each arc the length of the corresponding flight. A algorithm shortest path then solves the problem.
To take into account the duration of stopovers, two methods are possible: Edit the previous algorithm, including the stopover cost in the arcs OR: each vertex is duplicated; an arc between them is the corresponding city stopover.
Exercise 2
We want to build a new factory in the following network, the nodes are places and the links represent the costs to send energy from one place to another:
Based on the algorithm of Dijkstra, come up with a method to find the best place to build the factory, then solve the problem with your method. Solve the problem with the algorithm of Floyd–Warshall.
We need to calculate Dijkstra for each node (at source node). Once the path tree is created, add the cost of all paths from any node to the source node (add the last shortest paths array). The best place is the minimum total weight of all occurrences of Dijkstra. With Floyd-Warshall, the pseudo-closure matrix contains all arrays, just sum the entries of each array and find the minimum.
Exercise 3
A robot moves through the next environment. It starts from the node labeled start and must reach the node labeled end. The environment is continuous and the scale is provided in the figure. Considering the robot is a point, what is the shortest path from start to end.
Calculate the Euclidean distance between nodes. Draw the graph and apply Dijkstra's algorithm to find the shortest path from Star node to End node. Then draw the path in the figure.
Shortest path | Start | 1 | 2 | 3 | End |
Init | 0 | inf | inf | inf | inf |
Start | – | sqrt 5 | sqrt 29 | inf | inf |
1 | – | – | sqrt 29 | sqrt 5+ sqrt 26 | inf |
2 | – | – | – | sqrt 5+ sqrt 26 | sqrt 29 + sqrt 17 |
3 | – | – | – | – | sqrt 29 + sqrt 17 |
The shortest path is Start-2-End.
Exercise 4
Considering the graph of exercise 1, the edges are directed from left to right (or from top to bottom) and the weights are decreased by 4. How to find a minimal path from A to F? Solve.
Exercise 5
(a) Calculate the shortest path from s to all other vertices using Dijkstra's algorithm. Determine the shortest path tree.
(b) Is the shortest path tree unique?
(c) Now change the weight of edge (3, 4) to −2. Show that Dijkstra's algorithm does not work in this case.
(a) The solution is given by the following image. The numbers next to the vertices are the distances to the starting vertex and crossing out a number means there has been an update. The numbers in the squares indicate the final distances (shortest distances).
(b) None tree shortest path is unique. By replacing the edge (s, 3) by the edge (1, 2) we obtain another tree of shortest paths.
(c) Dijkstra's algorithm will give the same solution as in part (a) although the path (s, 1, 2, 3, 4) (dist 5) has a shorter distance than the path (s, 1 , 4) ( dist 6). Here's what happens: after visiting vertices s, 1, 2, the algorithm will search for the shortest path to a vertex not yet visited. This will be vertex 4 with distance 6. After visiting vertex 4, the algorithm will not update on vertex 4 because it has already been visited and for this reason cannot find the shortest path ( distance 5).
Exercise 6
A man has to carry a wolf, a goat and a cabbage across a river. He has a boat to do it with but it's so small he can only take one of the three things with him each time. Is it possible to get the three things across the river safely? Note that the Wolf and the Goat or the Goat and the Cabbage should never be on the same side of the river without human supervision. At least the wolf isn't a vegetarian and doesn't like to eat cabbage.
We construct a graph for this problem where each legal state is represented by a vertex in the graph and find a shortest path in this graph. Let S = {M,W,G, C} where M,W,G, C are the man, the wolf, the goat and the cabbage.
A state for this problem is a pair (X, Y ) where {X, Y } is a partition of S. The elements of X are always on the starting side of the river and the elements of Y are already on the other side . A state is a legal state if W,G ∈ X, Y ⇒ M ∈ X, Y and G, C ∈ X, Y ⇒ M ∈ X, Y, you cannot leave alone the cabbage and the wolf or the goat and cabbage unattended.
Let us now construct a graph G = (V, E) which has a vertex for each legal state of this problem. We have the directed edge (v1 , v2 ) ∈ E if we can go from state v1 = (X1 , Y1 ) to state v2 = (X2 , Y2 ) in a single boat trip on the river. All edges have weight ce = 1. Now the problem can be solved by calculating the shortest path from state (vertex) s = (S, -) to state (vertex) t = (-, S). We get 7 as the shortest path solution.
Exercise 7
Consider the following modification of Dijkstra's algorithm for working with negative weights: w(e) = c. Then for all edges f in E we set w'(f) := w(f) – c. Then G'= (V,E,w') has no negative weights. Does this version of the algorithm work correctly on this type of graph? Prove your assertion.
Now we claim that the algorithm does not work well on G' because this modification does not preserve the property of the shortest path, i.e. (-c) is a positive number, so you add n times for an n-path. The following counterexample proves this:
EN 
FR 
ES