0
$\begingroup$

If I just want to find shortest between a single source and destination, can I do better Dijkstra (which finds from one source to all destinations)?

I am trying to answer a question in the EPI book. The question is as follows: Suppose you are given a N*N matrix in which some of the cells are greyed out and two non-grayed out cells(source and destination), find the shortest path between the two. Greyed out cell means -> A path cannot traverse through that cell.

The book recommends DFS or BFS but this takes O(V + E) which in this case is O(N^2) since both number of Edges and vertices are O(N^2). Same as Dijkstra. Wondering is we can do better.

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ 1. That's not the same running time as Dijkstra's algorithm would have (check your reasoning). 2. Read about the A* algorithm. $\endgroup$ – D.W.♦ Jun 29 '16 at 6:45
  • $\begingroup$ Your SatNav which runs the problem with a few million nodes (a) assumes that each node has very few connections to other nodes, (b) takes advantage of the fact that the distances are not random, and (c) starts searching at both ends. (c) should always be applicable. $\endgroup$ – gnasher729 Jun 29 '16 at 7:52

Your Answer

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

Browse other questions tagged or ask your own question.