4
$\begingroup$

I was wondering what complexity a simple start-destination task in a routing software would have. Knowing the shortest path problem, it should be in P. Is there anything I am missing?

$\endgroup$
2
  • $\begingroup$ Welcome to the community, i would say that this is more a CS question. If my answer answered your question feel welcome to check the check mark. $\endgroup$ Sep 21 at 10:52
  • $\begingroup$ I think this question is within the scope of OR.SE, though of course it could be in scope at CS too. $\endgroup$
    – LarrySnyder610
    Sep 23 at 12:04
7
$\begingroup$

The prototypical graph search algorithm Dijkstra's algorithm for finding the shortest paths between nodes in a graph which works for unbounded non-negative weights has a time complexity for $O(|V|^2)$ where $|V|$ is the number of nodes/vertices in a graph which is in $P$.

There are special cases where further knowledge (such as heuristics) or the graph structure allow smaller upper bounds but those would also be polynomial as long as you traverse the graph itself. If you have an indexed random access, an accurate (signed) distance function and the graph is a 1d chain binary search could be used which is faster than linear but this is a very special case.

$\endgroup$
1
  • $\begingroup$ And look into A* search to understand Dijkstra can be improved. Peter Norvig (of the book "AI a Modern Approach") has some interesting youtube videos on the subject. $\endgroup$ Sep 21 at 11:47

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.