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?
$\begingroup$
$\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$– worldsmithhelperCommented Sep 21, 2021 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$– LarrySnyder610Commented Sep 23, 2021 at 12:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Sep 21, 2021 at 10:45
-
$\begingroup$ And look into
A* searchto understand Dijkstra can be improved. Peter Norvig (of the book "AI a Modern Approach") has some interesting youtube videos on the subject. $\endgroup$ Commented Sep 21, 2021 at 11:47