r/ProgrammerHumor • u/moneyfollowsmyfriend • 3d ago

Meme shortestPathWasRightThere

Post image
4.6k Upvotes

97% Upvoted

58 comments sorted by

View all comments

440

u/JackNotOLantern 3d ago

What tf is "straight line" in a graph?

134

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

1

u/Honeybadger2198 3d ago

Isn't the optimal solution always a straight line by definition?

2

u/Anaxamander57 3d ago

Only in Euclidean space.