0
$\begingroup$

So my lecture notes gave a "tabular" Dijkstra's algorithm which first constructs a distance matrix that contains the distances from every node $i$ to node $j$.

Then it proceeds:

List the node names in order (the example uses the alphabet). Take start node and write 0 beneath it, understrike it to signify that it's the final value, also list the distances to all the other nodes from the start node.

enter image description here

Move one row below and consider node B, write to it the shortest path (which coming from $A$ is 1). Then list all the distances to the other nodes as well, taking in account the distance that one came from $A$ to $B$. Again select the smallest path and understrike it for $B$. Continue ...

The final result in this case comes out to look like:

enter image description here

But particularly, since watching the def. for Dijkstra's algo in another site (https://brilliant.org/wiki/dijkstras-short-path-finder/), why doesn't one just take the shortest path directly? Why tabulate and construct distance matrices? Shouldn't it be clear that simply taking the shortest paths is both 1) most efficient and 2) feasible, since one knows all the distances.

$\endgroup$
4
$\begingroup$

I believe you are advocating for taking a greedy algorithm where you simply take the shortest path in front of you at any given point in time. One can instead imagine a graph that looks like this:

                                                 graph

A greedy algorithm would suggest to simply follow the strings of 1's to get from $A$ to $E$, however, we can see that the shortest path is not along the 1's, but the longest edge here. One could imagine extending this example, to where we have $n$ sides of length 1, and one side of length $n-1$.

From an outside perspective, we know all of the distances associated with each edge, but we do not know the cumulative distance from one node to any other, and this needs computation.

As can be seen, simply taking the shortest paths each time (from one node to the next) results in not always getting the true shortest path. You could instead say "lets find the set of distances of all paths from $A$ to $E$ and then take the shortest one", but then there is the question of how to do this efficiently. The answer to that is Dijkstra.

$\endgroup$
  • $\begingroup$ Okay so perhaps the tabular and the one given in the other link are the same algo, just that the other link explained it so that it seemed a bit different, requiring less data/memory. $\endgroup$ – mavavilj Aug 15 '18 at 20:26

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.