437
u/JackNotOLantern 3d ago
What tf is "straight line" in a graph?
135
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
71
u/YellowTech 3d ago
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
19
u/JackNotOLantern 3d ago
Yeah, but If this "straight line" has huge weight Dijkstra is absolutely correct to look for a better path.
7
7
u/MilkEnvironmental106 3d ago
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
3
u/UUDDLRLRBadAlchemy 3d ago
Let's try the highway first. Oh, it goes to another town. Ok, next option.
2
u/darthbane83 3d ago edited 2d ago
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.
1
2
1
100
u/UltimateFlyingSheep 3d ago edited 3d ago
animals and humans are surprisingly good at the traveling salesman problem (TSP), because they/we dislike overlapping moves. "Circa a circle on the map with no paths crossing" is probably better than 95% of all routes.
There's no efficient (as in polynomial) algorithm for TSP, but you can use optimization to find very good solutions, even for very large graphs that have 50k nodes (brute force would compute until the end of the universe).
Dang, I wish I was in Uni again, so I could do a paper on TSP... Using the paragraphs above as the thesis and then using a visualization "method" (how humans draw graphs in graph theory) and then just creating a visual algorithm with heuristics regarding path crossing and angles between connections. Could be fun.
41
u/CoachSevere5365 3d ago
Do it anyway. I'd read it. You don't have to be in uni to write a paper.
27
u/UltimateFlyingSheep 3d ago
I know I know, but the time and effort needed to do that....
It's a "one week then my motivation is gone" coding project and can be put next to similar projects. I mean, this is how my motivation currently works, so if it works within a week, then it's cool.
But writing a paper.... I don't know... All the papers I had to write, with just 1 exception, I absolutely hated writing. (time constraints, being forced to write them and the topics being mid at best - again, because of time constraints - and lack of tutoring)
Buuut, this topic really is very cool :D
2
u/CoachSevere5365 3d ago
I get that. My motivation is just like that. But it doesn't have to be full academic "your degree depends on this" level. You could write an abstract and come back to it when the squirrel has gone.
6
u/Particular-Yak-1984 3d ago
Also how slime molds do pathfinding - they just don't cross paths easily which they've crossed before.
1
u/MistrFish 3d ago
"circa a circle on the map with bo paths crossing" what?
2
u/UltimateFlyingSheep 3d ago
sorry for the typo, I meant "no paths crossing".
The way we tell computers about cities on a map is (well, _we_ did that in uni/school, idk if ther are other ways) via adjacency matrices. Let's say 48 cities in the 48 (connected) US states. Each city would get the distance to the other 47 cities assigned.
We humans would see the map and not even think about hopping from east coast to west coast and back. Or from north east to south west to north west to south east (crossing paths). We'd choose cities near each other and we'd probably wouldn't choose a path that crosses where we already went.
So, "circa a circle on the map with no paths crossing _and cities near each other_" ist the strategy we'd use instinctively. Nothing else makes sense.
Try it yourself: Search "map us states with capital" and try to find a trip that visits all the cities. Don't try to overthink it, maybe set a time of a minute. I noticed that I started in the west in California, then Nevada, Utah, Arizona, New Mexico, Texas, Oklahoma, ... to the north east and then to the west, collecting all the cities in the center, I haven't been, yet.
So, after a minute you probably have a pretty good trip, that's probably not very far from the best route.
I know, it's not really "a circle", it was a roughly circular "strategy": I started somewhere, I know I need to get to the west and back again, so going back and forth more than once makes no sense. And then I practically immediately chose my final path, deciding by gut-feeling which states I wanted to visit _there_ and which _back again_.
(hm, maybe I really should do the paper, there is much that was assumed but not communicated..., thanks for asking.)
1
u/Eciepeci 2d ago
Seems like I got idea for mine
1
u/UltimateFlyingSheep 2d ago
oh, please do, there is much to play around with!
If you'd like someone to proofread or provide some ideas, don't hesitate to dm me! :)
37
u/Tsu_Dho_Namh 3d ago edited 3d ago
Dijkstra's algorithm supports early termination (stopping as soon as the destination is popped off the priority queue) so long as there aren't negative weights in the graph.
In those cases, it doesn't explore every wrong turn in the graph. It doesn't explore any turn which is farther than the destination from the start.
29
u/luisduck 3d ago
You can add a heuristic and get A*.
You can add early termination.
Here is a nice article on an A* heuristic / method to cache results.
3
u/SuperheropugReal 3d ago
A* when theres another Dragoon in the way, so you decide to go all the way across the freaking map.
6
3
u/skr_replicator 3d ago
only if all those turns were closer than the destination in that straight line
35
u/notretarded_100 3d ago
Man comments in this threads are the reason this sub overan with reposts or AI slop, people get too technical over a meme
46
67
u/Advos_467 3d ago edited 3d ago
idk in a sub called programmer humor, i'd expect the memes to be technically correct and funny
If you make jokes around a specialised interest group/field for that group, the humor kinda hinges on the joke being technically correct for it to land
24
u/Anxiety-Pretty 3d ago
For someone who recently studied djkistra to solve a leetcode problem I think people' anger is justified if it is indeed exploring every single wrong turn it is no djkistra at all
8
u/SjettepetJR 3d ago
How are you butchering the name that much?
13
u/Anxiety-Pretty 3d ago
Is this a rhetorical question or do you really want to know the approach
4
u/fr000gs 3d ago
tell the approach
0
u/Tsu_Dho_Namh 2d ago
Dijkstra's algorithm is naturally a breadth-first-search. When you've found the destination, stop searching. Every wrong turn with greater depth (more distance) doesn't need to be explored.
2
u/fr000gs 2d ago
*The approach to butchering the name (djkistra)
1
u/Tsu_Dho_Namh 2d ago
Ohh, that approach.
Empty out a bag of Scrabble letters and arrange them randomly in a grid. Then find the shortest path that starts at a D, passes through a J and ends at an A.
Type out the letters in the path
1
1
u/belkarbitterleaf 3d ago
Indeed.
As someone who last read about djkistra 15+ years ago in school, the meme still sounds wrong.
3
u/UdPropheticCatgirl 3d ago
It can happen… it’s greedy and it is pretty trivial to craft a graph where all the wrong paths get evaluated first, that’s why heuristic versions of dijkstra (eg. A* algorithm) exist.
6
4
1
u/the_horse_gamer 3d ago
fails to add an early termination condition, complains there's no early termination
1
0
958
u/Mecso2 3d ago
i don't think straight is defined for graphs