CODEWITHSUNDEEP
algorithmgraphgraph-algorithmdijkstra
elexhobby
elexhobby

Reputation: 2668

Dijkstra's shortest path algorithm won't work

I have a graph with positive edge weights and positive node weights. The length of a path is defined as the sum of all the edge weights along the path, plus the maximum node weight encountered along the path.

I'd initially thought that a modified Dijkstra would work, but I found a test case where it would fail. How should I go about solving this problem? Are there any standard algorithms I should look at?

My modified Dijkstra is as follows: At each node I record the shortest path so far, and also the maximum node weight I've seen so far, and use that to calculate the length to neighboring nodes. Please see my comment for the details.

Here's a graph where Dijkstra fails: https://i.sstatic.net/YFnMn.jpg The numbers in green are the node labels. Everything in blue is weights (node and edge weights). Lets say I want to compute the shortest path between nodes 1 and 7 (labeled in green). The problem with Dijkstra is that the node 4 always records the path 1-8-9-4 since its shorter than path 1-2-3-4 (former length 9 vs latter length 13). But to reach node 7, path 1-8-9-4-5-6-7 is longer than 1-2-3-4-5-6-7.

Upvotes: 3

Views: 1339

Answers (2)

Κωστής Καρβουνιάρης
Κωστής Καρβουνιάρης

Reputation: 197

Your graph is not that clear to begin with (too many values in blue of unclear role), which makes answers even more difficult. A much better question, a simpler graph and some straight answers in this post.

What made it clear for me, and allowed me to correct my implementation and get the correct results, was that at the end of each repetition in the loop, when it was time to pick the next node/vertex, whose unvisited neighbours I should examine, I had to pick from the whole pool of unvisited vertices, not just from the unvisited neighbours of the currently examined node. I was under the false impression that once you pick a path at a crossroad, because the greedy nature of the algorithm takes you there, you can only follow it to the end, unvisited after unvisited node. No. You pick the next globally unvisited node each time based on the smallest tentative value, regardless of its position in the graph or whether it is connected to the current node.

I Hope that clears the confussion that others like me have experienced and has led them here.

Upvotes: 0

DanielV
DanielV

Reputation: 663

If you can forgive one order larger polynomial time, then fairly easy algorithm:

ModifiedShortestPath(u, v, G) {
  X = StandardardShorestPath(u, v, G);
  E = heaviest edge in X
  F = all edges in G of weight >= E
  Y = ModifiedShortestPath(u, v, G - F); // recur here on G without the F edges
  return Min(X, Y);
}

The runtime of this is |E| times more than your standard shortest path.

Upvotes: 0

Related Questions