My parents aren't home

My parents aren't home

If Dijkstra actually had to execute the algoritm by walking down the streets, note the cost of each intersection, and then go back and try the next one. It definitely wouldn't be the shortest path the first time around.

You're correct, Djikstra would have to traverse each route in order to sort the varying costs of each intersection and route.

Then again, if you've got all that information already, Djikstra could technically get the shortest route the first time round, provided route info, nodes and time costs are all provided for?

Everytime I see this algorithm I think of dijkstra from Witcher 3

Yes. And therein lies the issue. The algorithm assumes that the cost of discovering path cost is zero. Which is why it was extended into A*-search.

Good one, but why's the conversation in comic sans

I don't play that but I feel like if I did whenever I saw the character I'd think of this algorithm

I enjoyed this too much and I don't know why.

If Dijkstra had a fucking map, he could do that on paper and then walk the shortest path.

https://xkcd.com/1724/

Relevant.

Bae: come over Leonhard Euler: I can't, I'm in Königsberg, Prussia and I can't cross any bridge more than once Bae: my parents aren't home Euler: dammit.

A* is basically magic

Determining a decent heuristic function can be magic and is damn hard in most domains.

If Dijkstra had a map, he still couldn't do anything, because he's dead.

Image Transcription:

[The low resolution image begins with some simple Comic Sans text.]

Bae: Come over

Dijkstra: But there are so many routes to take and I don't know which one's the fastest

Bae: My parents aren't home

Dijkstra:

[The mobile Wikipedia page for Dijkstra's algorithm follows, including a diagram with nodes and some distances between them.]

Dijkstra's algorithm

Graph search algorithm

Not to be confused with Dykstra's protection algorithm.

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

The algorithm exists in many variants; Dijkstra's original variant found the shortest path between two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

I'm a human volunteer content transcriber for Reddit and you could be too! If you'd like more information on what we do and why ...

Pro Tip: Save this to a text file, this exact same meme gets posted every other week.

can confirm. Wife did not appreciate the graph theory jokes.

Asking the real questions... We don‘t deserve comic sans.

Didn’t that guy assassinate King Radovid?

This post is A*

I would give you A star for that algorithm

He needs to be able to optimize his routes with his fucked up ankle

But worst case it's just djisktras so any improvement at all will help

Then who is the girl talking to?

1: Think of a really good pun as a reply 2: Scroll down until you find the person who's already thought of it and posted it. 3: Upvote.

The internet makes things really convenient.

What if you would just intelligently guess the cost of an path? A kind of heuristic to help you guess it... ಠ‿↼

In Djikstra's algorithm for every node you visit you keep score of how far away it is from the starting node. When you need to pick the next node to visit you choose the one with the lowest score (i.e. closest to the start). This means you explore in all directions evenly from the start node until you find the end node.

In A* you also use a heuristic (a guess) of how close you are to the end node. On a grid where each node is a grid-square, for example, the heuristic could be a straight line distance from your current node to the end node whilst ignoring any obstacles. So in A* when you choose the next node to visit you still pick the one with the lowest score, only this time the score is derived from "distance from start" + "guessed distance to end". This means instead of exploring all directions evenly you are biased towards (more likely to move towards,) the end point.

Okay, a medium to large.

True. I had to implement this in an A.I. course I took in graduate school for the Blocks World game (Think Towers of Hanoi). The focus mainly on the heuristic and just using a basic heuristic such as stack distance proves to be very ineffective. Fun little assignment to work on though.

Basically, they're totally different problems.

Dijkstra's Algorithm gives you the shortest route from a starting node (say A) to every other node in the network, so the shortest route from A->B, A->C and so on. It makes no guarantees as to which nodes are visited to get from A->B, only that it's the shortest path.

Travelling Salesman is the shortest path from A, through every node in the network and back to A. Dijkstra's could tell you the best path from A to the furthest node, but you need to include all the other nodes it ignored as well.

Depends on the scale. If you're walking 100 feet it's not going to make much difference, but if you're planning a route from coast to coast of the USA it's certainly worth the hour or so it would take to do the calculations (assuming each interstate is an edge and each intersection of interstates is a vertex).

A medium.

You've stumbled across 'the hard part'. A* is only as good a the heuristic you choose. If you go back to the grid example which is easy to visualize (and also why it's used as an introduction in things like game design,) the heuristic used is the straight line distance between the current node and the end node. You can work that out with Pythagoras. If you're trying to avoid square-root calculations for speed it is common to use the Manhattan distance, i.e. distance on the x axis + distance on the y axis. Once you move beyond uniform grids and onto more complex graphs the heuristic becomes more difficult to calculate.

with less pixels too...

If only there were an algorithm for figuring out which algorithm to use.

Good point.

Did I miss something?

Even so, would working out the algorithm and applying it to a map produce a decrease in travel time that counters out the amount of time it took to work out the algorithm and apply it?

A quick guess seems like the optimal algorithm here, if we're minimizing total time to objective.

Depends on how complex the map is and how far the girl lives away. If she lives at the other end of the world, taking a few days off to develop an algorithm and calculate the shortest path before walking to her house should be worth it. Then again, in this case her parents are probably home again until you arrive.

he put the conversation in comic sans so you know it's a joke

It's all you can think about during that portion of the game.

It gets reposted often. I'm glad for every time.

If only there was an algorithm for traversing every edge of a map...

He may fail depending on your play through and dies.

I’m about to study that this week. Care to do a ELI5?

A medium what?

This is a repost this is the original (i think): https://www.reddit.com/comments/5sg8dj

But this guy I answered said that Dijkstra is walking. By walking, shortest distance and shortest time are pretty much the same. If he's driving, getting up-to-date data about the traffic is a completely new problem.

First thing that popped in to my mind. Him being a spy and all I bet he actually could help out.

According to the screenshot this tryst occurred in 1956, bud.

Karma / views farmer. Do not click any link

[-]timede23rt

it's the name of a character in the game... that's basically it

That's why AStar always gets the girls, "As the crow flies" he says, fucking asshole.

Not to be confused with Dykstra's protection algorithm.

I didn't even notice this in the picture. That just adds a whole other layer to the joke.

Here is an explanation I made on a previous thread. Note: In my explanation, Uniform Cost Search is Dijkstra’s Algorithm

—-

A* is very clear to understand, but you should have an understanding of what DFS, BFS, UCS, and A search before trying to learn A* search.

Uninformed Searches (no information about the problem):

Depth First Search (DFS) - Uses a Stack to store and select the next node to explore. Breadth First Search (BFS) - Uses a Queue to store and select the next node to explore. Uniform Cost Search (UCS) - Uses a Priority Queue to store and select the next node to explore. This priority queue stores a (node, totalCostFromStartNode(node)). Where BFS and DFS can't handle costs between nodes, UCS can handle graphs with different costs.

Informed Searches (information about the problem, usually represented as a heuristic):

A Search - Same as UCS, but instead uses (node, totalCostFromStart(node) + heuristicCostToClosestGoal(node)). Heuristics are basically estimates/guesses. For A search there is no constraint on how good/bad this heuristic actually is to the trueCostToClosestGoal(node).

A* Search - Same as A search, but heuristicCostToClosestGoal(node) must be admissible. Admissible heuristics are always optimistic, they are always <= trueCostToTheClosestGoal(node). For A*, the heuristic must also be non-negative.

Hope this answer helps, if you have any more questions let me know.


Needs more jpeg


There you go!

I am a bot

Needs more jpeg

I am a bot

Hey I remember having to code a similar thing in my network class!

This is brilliant, thank you!

So it took him 3 years to reach his GF? Read the Article.