Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
It depends on whether you want an efficient solution that works most of the time or a solution that's less efficient but works all of the time. Dijkstra's algorithm is a "greedy algorithm" and thus doesn't work 100% of the time.
I'm thinking something like a recursive solution, where at each vertex you traverse to each of the immediate neighbors, returning the shortest path at each level. Of course, you have to keep track of the visited vertices so as to not get into any loops.
Hope you didnt understand the Greedy algorithm concept.
The solution which you suggested is itself a Greedy-Dijkstra algorithm.
No it isn't. My explanation for my recursive solution wasn't very good, so I'll provide code later to show you what I mean.
Here is an excerpt from wikipedia's entry on "greedy algorithms":
Greedy algorithms mostly (but not always) fail to find the globally optimal solution, because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early which prevent them from finding the best overall solution later. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum.
If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it is faster than other optimisation methods like dynamic programming. Examples of such greedy algorithms are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees, Dijkstra's algorithm for finding single-source shortest paths, and the algorithm for finding optimum Huffman trees.
My apologies. I originally didn't see it specified that this was for positive arc paths only. It seems Dijkstra's algorithm does work for positive arc paths.
Argument1:
Greedy algorithms dont work find for all the problems. It is true, that does not mean that in single-source-shortest-path-problem dijkstra's wont provide correct solution all the time.
Greedy algorithms wont work in some problems as in travelling sales man problem. There the Greedy-solution may lead to a city where all the paths are traversed and there is no untraversed way to go a next city. Thus for problem TSP it is not a 100 solution. BUT Greedy-Algorithm has a way to find single-source-shortest-path-problem correct all the time. Using dijkstra's.
Argument2:
As Problem is to find the shortest-path between two nodes where as Dijkstra's produces shortest-path tree, just run the Dijkstra's algorithm till you find the destination node. Report once you traverse the destination node instead of going for all nodes.
Use Dijkstras algorithm
- dini June 16, 2012