3 ms·
Sorry, you're right. My recent work has involved pathological cases of dynamic spanning trees, and I've recently proved that a sub-class is NPC, and I mis-spok
by RiderOfGiraffes 17y ago
Sorry, you're right. My recent work has involved pathological cases of dynamic spanning trees, and I've recently proved that a sub-class is NPC, and I mis-spoke myself here. The SatNav problem is obviously easier. Given the power of the processor, limited memory, and complexity of streets (in the places I typically deal with) I still find it surprising.
But you're right. Dijkstra's algorithm clearly solves this problem simply enough in O((|E|+|V|) log |V|) for the sparse case.
Apologies.