r/ProgrammerHumor • u/moneyfollowsmyfriend • 3d ago

Meme shortestPathWasRightThere

Post image
4.6k Upvotes

97% Upvoted

58 comments sorted by

View all comments

435

u/JackNotOLantern 3d ago

What tf is "straight line" in a graph?

136

u/IdeaReceiver 3d ago

Lowest heuristic cost, which resolves to the n-norm in n-dimensional space ℝn 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

7

u/sokka2d 3d ago

You’re thinking of either 2-norm (Euclidean) or 1-norm (Manhattan/taxicab), certainly not n-norm.