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?
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.