There is the following task: to find the minimum path and find the second minimal path, while the second minimal path should not completely contain the first minimal path.

Examples ("1)" - the minimum path, "2)" - the second minimum path, the node numbers are indicated): 1.1) 1-3-5 2) 1-2-3-4-5 2 way completely contains the first.

2.1) 1-3-5 2) 1-2-5 2 path does not contain 3 node with 1 path.

3.1) 1-3-5 2) 2-4-5 It can also be correctly correct.

The implementation of the algorithm is as follows:

  1. Using Dijkstra's algorithm to find the first minimum path.
  2. Write the resulting minimum path (i.e. node numbers) to the array.
  3. ?????? And actually there is a problem - how to start finding the next minimal paths. The assumption that the second minimum value is the second minimum distance of the neighbors of the target node (Example: there is a target node N with neighbors N-1 (distance - 6) N-2 (8) N-3 (11), that is, theoretically the second minimum is the path through N-2) is not always true. you may need to change the node in the first way in the middle and get a smaller value (in the example you will need to change the used N-8-> N-5 edge with a weight of 1 to the edge of N-9-> N-5 with a weight on the way to N-1 2, the distances to N-8 and N-9 are identical, and then we get the minimum way with a weight of 7).

The question is how to find this second way?

  • The thought occurred to vskidku to take turns to break one edge from the minimum route and recalculate the network. The minimum of the found routes is the right one. Only it seems to me that it is too "expensive" to recount the network several times ... - Mike
  • @Mike I tried it, it works, but it is really expensive (because on tests in minimum paths of 100 knots). As a result, I can’t pass tests on time. Are there any other options? - Ihor Kyrychok
  • I am a little far from this subject, so if I have no good approaches, I don’t know them. Here I think that it would be possible to tear not all the edges of the route, but only some, focusing on their weight, but which ones to choose xs. And I also think it would be possible to re-calculate not the entire network, but only nodes in the weight of which there is a torn section, but the first problem is to find out these nodes, the second problem and the main one in terms of node weight can affect the weight of some other nodes and even we will understand how this reaction to the whole network will spread: ( - Mike

1 answer 1

After Dijkstra worked for the starting vertex, we got an array d1 [] shortest distances from the starting point to any, now we start Dijkstu a second time, just from the finish, we get an array d2 [] the shortest distances from the finishing point to any. Now we go through all the vertices that do not belong to the shortest path, and find a vertex v for which d1 [v] + d2 [v] is the lowest possible, and the second shortest path (with long d1 [v] + d2 [v]).

Pseudocode:

1. shortestPath, d1[] = Dijkstra(start) 2. d2 = Dijkstra(finish) 3. dist = infinity, w = -1 for (v : AllVertices \ shortestPath) if (d1[v] + d2[v] < dist) dist = d1[v] + d2[v], w = v 4. Восстанавливаем кратчайший путь от start до w и добавляем кратчайший путь от w до finish - это и будет второй кратчайший путь

The time complexity will coincide with the complexity of Dijkstra, so it is impossible to come up with something much faster :)

True, this solution does not guarantee that the second minimal path will not fully contain the first minimal path (: But it seems to me that it can be easy to add.