2
$\begingroup$

We know that the FW all pair shortest path is a Dynamic Programming (DP) approach to solving the problem. Being a DP, it smartly evaluates all possible options before deciding the final option at each stage.

I have manually evaluated and traced a 5 node graph with this algorithm. The actual graph is not important here. I will take the example of the evaluation of path(V4,V5) in iteration 1 and 2 only:

Stage 1: min{(4,5),(4,1,5)} of Stage 0

Stage 2: min{(4,5), (4,2,5)} of Stage 1

So if we expand this, then by the end of Stage 2, we have actually essentially evaluated the paths {(4,5) , (4,1,5), (4,2,5), (4,2,1,5), (4,1,2,1,5)} and selected the minimum.

As seen, we are evaluating cyclic paths as well e.g. (4,1,2,1,5) from above. If we continue tracing the algorithm till the end, we find that we never evaluate the path (4,2,1,2,5) for this specific example. Does this mean, not all paths are evaluated with this algorithm? I know not evaluating it won't harm as it will definitely not be the shortest path but my point is that should have been the case with (4,1,2,1,5) too. It looks like although the output is correct and consistent, yet theoretically speaking certain paths are not evaluated because of the way the algorithm is structured and not out of merit. Am I missing something here?

Improve this question
$\endgroup$
1
$\begingroup$

Yes, the path $(4,2,1,2,5)$ is not evaluated. However this is not a problem.

Since we assume that the graph doesn't contain any negative cycles (this is a requirement for FW), there exists an optimal path for each pair of nodes that doesn't contain any cycles. Therefore the algorithm only needs to guarantee, that cycle-less path gets evaluated.

By induction you can show that this is always the case. Let $k$ be the variable in the most outer loop. Induction hypothesis: After the $k$th iteration the table contains all the shortest paths between each pair that only uses nodes $\le k$ on the path (without start and end node).

At the beginning this is trivially true. And also the induction step, going from $k$ to $k+1$, is pretty easy to show: A minimal path using only nodes $\le k + 1$ from $u$ to $v$ either contains only nodes $\le k$, or it contains a minimal path from $u$ to $k+1$ combined with the minimal path from $k+1$ to $v$. (Here we use the fact that the paths contain no cycles. If a path contains cycles, this statement ca be wrong.) And exactly this case is handled in the algorithms.

Therefore at the end the table contains all minimal paths.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks Jakube for confirming... to quote you "Therefore the algorithm only needs to guarantee, that cycle-less path gets evaluated"; this is exactly where I see a "harmless inconsistency" in the approach although the end result is correct. As you can see (4,2,1,2,5) which is a cycle is not evaluated but (4,1,2,1,5) which is also a cycle is in fact evaluated. This inconsistency as I see it stems from the way the algorithm is structured and not based on merit. Your thoughts? $\endgroup$ – Sheel Pancholi Feb 19 '19 at 10:50
  • 1
    $\begingroup$ We don't need to evaluate any paths containing cycles at all. So it's not necessary to evaluate neither (4,2,1,2,5) nor (4,1,2,1,5). So it's only a "nice bonus" that it also evaluates the path (4, 1, 2, 1, 5). I wouldn't call that an "inconsistency" however, since that's not the goal of the algorithm to only examine cycle-less paths. The goal of the algorithm is to find the shortest paths, using the induction hypothesis described in my answer. And that one is completely guaranteed. $\endgroup$ – Jakube Feb 19 '19 at 11:10
  • $\begingroup$ Alright; thank you so much; that is a much better way of putting it. $\endgroup$ – Sheel Pancholi Feb 19 '19 at 11:13
  • $\begingroup$ @SheelPancholi: I would put it this way: Cyclic paths like 41215 are "noise" that FW evaluates "accidentally", because it would be too much work to avoid evaluating them. Fortunately they are harmless here, because whenever we evaluate a path containing a cycle as a candidate solution to some subproblem, we will certainly also evaluate a non-cyclic path of at most the same length as a candidate solution for that same subproblem: specifically, that same path but with the cycle deleted. (The no negative cycle condition ensures that this non-cyclic path cannot weigh more.) $\endgroup$ – j_random_hacker Feb 19 '19 at 12:04
  • $\begingroup$ Alright this makes sense. $\endgroup$ – Sheel Pancholi Feb 19 '19 at 13:19
1
$\begingroup$

Being a DP, it smartly evaluates all possible options before deciding the final option at each stage.

I think this is a misrepresentation of what DP means. Dynamic programming is basically divide-and-conquer with memoisation. For problems whose solutions have the right structure it guarantees to find the optimal solution, but it doesn't guarantee to evaluate the entire solution space: a DP algorithm can freely discard parts of the solution space which are demonstrably incapable of contributing to an optimal solution.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.