Eli5: what is dijkstras algorithm?

218 views

I’m a cs student and am so lost

In: 2

Anonymous 0 Comments

It’s a method for finding shortest travel distance/costs in a graph (think of this as a bunch of points and lines).

If you’re going to a store. you live on 1st street (S), the store is on 3rd street (D). You can go one blocks east, two blocks south and one block west (route a). But that’s 4 blocks. Or you could go 2 blocks south (route b).

Computers don’t ‘know’ directions, they just know numbers.

Dijkstra’s algorithm just visits every route possible in the map and keeps track of the shortest distance.

it’s used for GPS directions. You can use things like traffic, distance, etc for the ‘cost’ of each segment. Maybe the b route has heavy traffic and would take 5X as long. In that case the a route would be ‘shorter’

+—-Saaaaa—- 1st st
| b a
+—-b—-a—- 2nd st
| b a
+—-Daaaaa—- 3rd st

The way it works is it keeps a list of all the nodes visited, and the cost to visit them

a-<–S->–b—- 1st st
| v |
c—-d—-e—- 2nd st
| | |
f—-D—-g—- 3rd st

it visits all the nodes reachable from S (a,b,d). then has [Sa=1, Sb=1, Sd=1]

then it visits say all nodes reachable from b (e) then [Sa=1, Sb=1, Sd=1, Sbe=2]

then it visits all nodes reachable from e (d, g). But Sbed is 3 and Sd is already ==1. So it throws that away [Sa=1, Sb=1, Sd=1, Sbe=2, Sbeg=3]

It knows which links have already been visited, so it doesn’t duplicate