Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Dijkstra's algorithm only applies if all entries are non-negative, not just the overall distance between the source and destination. This assumption was not explicitly stated. You cannot infer that from "path".
Still, you could ask the interviewer whether all values are non-negative, and if they are all non-negative, you'd be set.
Yes the regular greedy Dijkstra's Algorithm will work on a regular matrix with non-negative numbers. But it does not work for graph with negative edges.
Here is the dynamic programming solution to the problem:
Let Opt(x,i) : optimal solution from the xth entry in the matrix to the end using i entries.
foreach neighbor of x:
Case1: either the neighbor will not be in the solution:
Which means that Opt(x,i) = Opt(x,i-1)
Case2: one of the neighbors will be in the solution:
Which means that for each neighbor w of x: Opt(x,i) = MIN ( val[w]+Opt(w,i-1))
The solution will be the minimum of Case1 and Case2.
Hence answer:
foreach neighbor w of x
Opt(x,i) = MIN (Opt(x,i-1), MIN(val[w]+Opt(w,i-1)));
Reference: Shortest path problem on a graph with negative edges (Chapter on Dynamic Programming, Jon Klienberg).
since question says path, we can assume that the distance cannot be negative.
- msramachandran October 25, 2011Visualize the matrix as graph and apply Dijkstra's algorithm to get the shortest path.