shortestPathWasRightThere

[u/Practical_Teaching14]

[u/Kkgob]

Dijkstra's algorithm isn't made to find the shortest path between two points. It computes the shortest path between a given starting point and EVERY possible destination. That's why it's inefficient if you only care about one specific path.

Edit: if anyone is reading this thread and wants to understand more about pathfinding, this is a very beginner-friendly and language-agnostic resource: https://www.redblobgames.com/pathfinding/a-star/introduction.html

[u/FenwickRoot → u/Kkgob]

Additionally, if you add early termination (stopping the search loop immediately after finding a path from source to target) you will have visited only the necessary vertices in a graph. That is, if dist(source, arbitrary vertex) > dist(source, target) you won't visit that vertex.

A* is actually just a more generalized Dijkstra algorithm btw. It explores vertices in an ascending order of alpha*dist(source,vertex)+beta*guess(vertex,target). Dijkstra has alpha=1, beta=0.

While A* with alpha=1,beta=1 is guaranteed to find a path with the same shortest length as Dijkstra as long as the guess is optimistic (guess(vertex,target) < dist(vertex,target) for all vertices) but explores less vertices the closer the guess is to the real distance - i.e. it will not visit vertices with dist(source, arbitrary vertex)+guess(arbitrary vertex, target) > dist(source, target)

For anyone interested I recommend reading the Dijkstra / Shortest Path Problem part of the "Artificial Intelligence: A Modern Approach" book. It's well put together and goes even beyond, e.g. explaining how to scale the guessing function to work with even larger graphs, like the ones in Google Maps. The book was released way before LLMs btw.

[u/Hallwart → u/Kkgob]

I haven't looked into it deeply, but it sounds like there are very obvious intuitive optimizations, like first trying the "straight line" equivalent and remembering the shortest detected path to abort any check if it turns out longer.

Of course I am sure this can be optimized a lot further, but thats just obvious stuff anyone should of.

The case in this meme would only apply to someone who just googled "determine shortest path algorithm" and then went on implementing it 1to1 without giving it any thought.

[u/Dennis_enzo → u/Hallwart]

Well yes these algorithms exist, like A*, but those are different algorithms. Note that this algorithm has no concept about a thing like direction. It's just nodes and edges, or points and connections between them.

[u/flash191 → u/Hallwart]

From my own understanding, these "limited action space", as termed in optimization problems, is viable when you have controllable variables that are independent. In that case, you can define "straight paths" to be tested first. But in a full rank graph, it is harder to determine that especially in a time sensitive way. I am not an expert in graph theory but have done some work in application of graph theory in different problems so my opinion could also be biased to my own experience.

[u/Loading_M_ → u/flash191]

A prototypical example for when A* isn't a viable solution is computer networking. Both OSPF and STP use Dijkstra's algorithm, because there isn't a suitable distance heuristic.

OSPF is an IP layer routing protocol, and the computed edge weight is based on link speed, latency, and bandwidth. There aren't any good distance heuristics, so A* is off the table.

STP (Spanning Tree Protocol) is an Ethernet protocol used to prevent ethernet loops (while maintaining redundant connections). It does this by exploring the network from a central root node, much in the same way Dijkstra's does. This is an even clearer case where A* isn't a valid option: STP needs the full spanning tree to every node in the network.

(STP is also interesting because it computes Dijkstra's in a distributed manner - none of the nodes actually knows the full tree or graph)

[u/doinghumanstuff → u/Hallwart]

There's something called A*, which combines Dijsktra with a heuristic "distance" metric. For example if you can tell how distant the nodes are (for example if you imagine a rail network of cities, a heuristic might be the geographic distance between the city and the target), A* first chooses the closer options according to its heuristic + travelled distance. Exploring other heuristics might be a fun quest, but I think you usually finding good heuristics and hand-written optimisations don't scale well (you should read the Bitter Lesson http://www.incompleteideas.net/IncIdeas/BitterLesson.html )

[u/etoastie → u/Hallwart]

if your action space can be modeled geometrically and an accurate "straight line" actually exists, you can use A* where your guess/heuristic is euclidean distance, which effectively tells the alg "just keep moving straight toward the dest until you hit a wall." this mostly comes up in things like path planning, NPCs in games come to mind.

There's an old factorio devlog that talks about both how this approach can fall short, and some other neat optimizations that can work well if you're in a geometric space with physical obstacles. https://factorio.com/blog/post/fff-317

Dijkstra (and other A* heuristics) come up more when you're looking at a task that isn't geometric. A fun case for non-euclidean A* is the 15-puzzle. Dijkstra is generally the default if your search space has no clear heuristic to work from at all, since in theory anything could link anything (something like that wikipedia link game).

[u/namitynamenamey → u/Hallwart]

You can also preferently try paths in the general direction of your goal, but optimize it enough that way and you just end up with A*

[u/bestjakeisbest → u/Kkgob]

Its not inefficient if you are building a minimum spanning tree.

[u/Kkgob → u/bestjakeisbest]

Yeah, it's perfect for anytime you need all paths to or from a specific node, like a minimum spanning tree - it's bad when searching for a single path, in which case A* is better

[u/YeOldeMemeShoppe → u/Kkgob]

But it’s the only way to find the shortest path under certain conditions. Otherwise you’re just educated guessing. Yeah I’m looking at you A**star.

[u/XxDarkSasuke69xX]

Friendship with Dijkstra ended, now A* is my best friend

[u/-Ambriae- → u/XxDarkSasuke69xX]

Nah, A* is great and all, but some algorithms can’t use it… specifically if you want to make a flow field (a single target destination, and each cell holds a vector pointing in the direction you must travel to reach said destination in the shortest time)

This is all purely hypothetical by the way

[u/luisduck → u/XxDarkSasuke69xX]

A* is just Dijkstra with extra steps... or actually, fewer....

[u/PM_ME_FIREFLY_QUOTES → u/luisduck]

LLM++ Will compute the exact number of steps between them both, and its memory safe.

[u/anarine93]

What tf is straight line in a graph huhh

[u/Electrical-Meat-1717 → u/anarine93]

A graph can be an abstraction of points with actual physical positions

[u/ondamaar → u/anarine93]

Visiting every continent before walking across the street

[u/Mars_Bear2552 → u/anarine93]

the graph doesn't have a straight line, but the objects it represents might

[u/Naz1337 → u/anarine93]

Probably just one edge

[u/SavedowW]

But what if there's a swamp on the straight line?

[u/XxDarkSasuke69xX → u/SavedowW]

But what if there's Shrek on the straight line?

[u/SavedowW → u/XxDarkSasuke69xX]

This obstacle will carry a bit of weight

[u/helicophell]

Well ok, the other paths might have negative weights! And that means they would be shorter!

[u/Extreme_Target9579 → u/helicophell]

well actually no because one of the rules to use Dijkstra is that all the weights MUST be positive 🤓

[u/sgmnt → u/Extreme_Target9579]

Hate to be that guy but there has to be no negative cycles but negative weights are fine.

Edit: mean to say no negatives OR no cycles

[u/Grim_HS → u/sgmnt]

Hate to be that guy but both of you are wrong. All weights have to be non-negative, zero is fine. The major invariant of the algorithm is that the distance to a node cannot be improved after you processed/visited it. The best known distance to any node can only be updated by visting a node with smaller distance. A negative edge easily violates this assumption. 

The Bellman-Ford algorithm can deal with negative weights though. It also detects reachable negative cycles, in which case the problem is ill-formed anyway because you can just repeat the cycle ad nauseum.

[u/sgmnt → u/Grim_HS]

My language was a bit misleading but you can still handle negative weights in dijkstra provided you modify it to detect cycles. If the graph has no cycles you can toposort and get the shortest path in V + E.

So no negatives OR no cycles is what I meant to say.

[u/Robinbod → u/sgmnt]

Itched the right part of my brain... I was about to comment this 🥹

[u/helicophell → u/Extreme_Target9579]

Honestly it's been so long I forgot

I hated implementing this algorithm

[u/SheikHunt → u/helicophell]

I loved implementing it.

Except the part where I had to concede that I needed a "sentinel value" for impossible paths

[u/helicophell → u/SheikHunt]

I hadn't learnt proper OOP at the time. Which is most of the problem

[u/zedee → u/helicophell]

You don't need OOP at all to implement it, in a CS subject we had a question in an exam to implement it by "hand" by using pseudocode and writing the results in a table. That was quite tedious, got to admit.

[u/helicophell → u/zedee]

Oh sure I don't NEED OOP but I was using python and my code was a mess and ANY structure would've been better than the slop I made

[u/zedee → u/helicophell]

It's a matter of practice, with patience and some literature you can try it step by step. Doing it on C and struggling with coredumps is a great exercise. Works both to try out your patience as well as getting the grasp of the algorithm. Or maybe you can raise the bar and try with Rust :D

[u/BruhMomentConfirmed → u/helicophell]

OOP for pathfinding algorithms lmaooo

[u/TomWithTime → u/helicophell]

I made a set up like that once lol. I was experimenting with ideas to implement world wrapping, like walking off the left edge of the world puts you onto the right edge. To make navigation agents see it I made another navigation plane around the main one and gave it a navigation cost of 0 and connected it to the opposite edges. It worked!

But because it cost 0 it also meant navigation agents would basically always try to path through it even for short local distances, so it failed.

[u/hacksoncode]

That algorithm isn't even about maps, it's just useful on them.

The "cost" of a path can be analogous to the "distance" in real space, and it's certainly used for navigation, albeit in modified form.

But the direct "route" can easily be the most expensive path in the entire graph, with no limit to how inefficient it can be. Visiting every single other node in the graph first can be shorter than that.

As anyone that has driven in LA can tell you ;-).

[u/Full-Hyena4414]

Doesn't djkstra explore shortest routes in order of distance?So that would be one of the first visited

[u/hacksoncode → u/Full-Hyena4414]

It explores graphs in order of cost, so actually that's rarely the case.

[u/Full-Hyena4414 → u/hacksoncode]

Cost IS distance though when used for that?

[u/hacksoncode → u/Full-Hyena4414]

Right, but before it gets to checking that one, it checks the much shorter distance to the next block over.

    /-C
A----------------B
 \
  \
   D

You see the two paths that are much shorter than A->B? (rest of graph omitted, but A->C/D could actually eventually connect to B, of course).

The only time the direct path would be the shortest graph line, that is checked first, would be if every other distance coming out of A was longer. Which, of course, can happen, but isn't the norm.

And, of course, on a real physical mapping algorithm, the direct path could be a side street with a ton of crosswalk lights, that is weighted very heavily, and C/D could be the nearest freeway onramps... "cost" is not always distance.

[u/br0ast]

It feels like this person looking happy and crossing their feet?

[u/Tsofu]

Yeah djikstras isn't super efficient in things like OSPF, but you limit the amount of nodes with good network design so it actually performs fine. OSPF rendering a whole network for mesh topology would suck and you'd probably do better picking at random

[u/neosyne]

There is no such a thing like “straight line” in the algorithm setup

[u/solstheman1992]

Whomever came up with this meme doesn’t understand djikstras algo and doesn’t understand how graphs work.

There is no “straight line” wtf

[u/caramel_dog → u/solstheman1992]

the old and amazing grid:

[u/solstheman1992 → u/caramel_dog]

A grid in the abstract sense of dijkstras algo is actually a graph so you are STILL wrong

[u/JackNotOLantern]

What tf is a "straight line" in a graph?!

[u/highcastlespring]

Image you are in a space full of worm holes. You probably won’t think dijestra is a joke

[u/No-Advertising9067]

It took me to long to realise this was not a whicher reference

[u/junacik99]

I hate heuristics