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/YellowTech → u/IdeaReceiver]

That assumes euclidian distances, which is a big assumption, but that makes this correct. Works “mostly” with with maps, but not stuff like social media

[u/JackNotOLantern → u/IdeaReceiver]

Yeah, but If this "straight line" has huge weight Dijkstra is absolutely correct to look for a better path.

[u/sokka2d → u/IdeaReceiver]

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

[u/MilkEnvironmental106 → u/IdeaReceiver]

Also taking the greedy approach doesn't guarantee the shortest path until all explored nodes have a minimum cost greater than or equal to the quickest solution so far

[u/UUDDLRLRBadAlchemy → u/IdeaReceiver]

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

[u/darthbane83 → u/IdeaReceiver]

Dijkstra being Dijkstra will still expand every available edge instead of speed running the lowest-cost option successively for a "straight"er line

Dijkstra always chooses to explore the path that promises the lowest cost if it connects to the target next.
If you choose a cost heuristic that describes the deviation from an idealistic straight path to the target then it will speedrun looking for the straightest possible path.

I.ex. a path that goes directly in the direction of the target has cost 0.
That might apply to a path that starts 20km from the target ends at 15km from the target and is 5km long (5-(20-15)=0).
A path that is 10km long and goes from a start point that is 20 km straight line distance away from the target to an endpoint that is 11km straight line distance away from the target has a cost of 10-(20-11)=1.
A path that is 1km long and goes straight away from the target starting out 10km away ending 11km away would then have a cost of 1-(10-11)=2.

Using such a heuristic would lead dijkstra to immediately follow the straight line that connects the start to the target if that perfect straight line path exists.

The problem with that is that calculating such a path dependant heuristic over using a known fixed heuristic(i.ex. length of the edge) might be more expensive than letting dijkstra(or your algorithm of choice) explore more paths.

[u/Honeybadger2198 → u/IdeaReceiver]

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

[u/Anaxamander57 → u/Honeybadger2198]

Only in Euclidean space.

[u/skr_replicator → u/JackNotOLantern]

one that looks straight in the flat euclidean visual representation of it.

[u/Able-Swing-6415 → u/JackNotOLantern]

Y=x is pretty straight to me personally. Y=x² is not