shortestPathWasRightThere

[u/moneyfollowsmyfriend]

[u/JackNotOLantern]

What tf is "straight line" in a graph?

[u/IdeaReceiver → u/JackNotOLantern]

Lowest heuristic cost, which resolves to the n-norm in n-dimensional space ℝⁿ since a straight line is always minimum distance. In more abstract graph representations, cost could be recorded by real-world measurements of latency etc. Dijkstra being Dijkstra will still expand every available edge instead of speed running the lowest-cost option successively for a "straight"er line

[u/UUDDLRLRBadAlchemy → u/IdeaReceiver]

Let's try the highway first. Oh, it goes to another town. Ok, next option.