CODEWITHSUNDEEP
algorithmgraph-algorithmdijkstra
BubbleTea
BubbleTea

Reputation: 219

Trying to understand how Dijkstra's algorithm works via a simple example

I want to get from a to d via the shorter route (lowest cost)

  1    15
a--->b---->d
|        /\
|2       /
|       /1
|      /
|     /
|    /
|   /
|  /
| /
\/
c

a can go to b at a cost of 1 or c at a cost of 2. b can go to d at a cost of 15. c can go to d at a cost of 1.

Wouldn't the algorithm start with a->b because it has a cost of 1 versus a->c which has a cost of 2? But then it can only go from b->d at a cost of 15 which is more costly than if it had gone from a->c->d

I'm trying to freshen up on this algorithm so please tell me if my logic is flawed.

Upvotes: 1

Views: 957

Answers (4)

Tacet
Tacet

Reputation: 1421

Mistake is think "the first way, the best way", it isn't true. In this algorithm you can update the cost of reaching to vertex (if it is warranted by lower cost).

Nodes are divided into visited, unvisited, available, unavailable.

We can don't think about visited, because if, he had the smallest value, and we haven't negative-value edge (see algorithm assumptions) you can't find better way.

Unvisited are all another, possible that we can't actually walk to all of them.

Available vertices are all unvisited, which we can visit now. (Unavailable is obvious, I think.)

At start available is only first vertex. We can follow a simple pattern.

Step by Step:

-Take the least expensive vertex from all (actually) available. This should be done by the priority queue. The simplest solution is a binary heap (O(|E| log |V|)), but if you thinking about performance, you can use Fibonacci heaps (O(|E|+|V|log|V|)), if don't, possible, but not recommended means is to use an array (O(|V|^2+E)). This should be the root.

-For the current node you should update all unvisited neighbours (unvisited, no unavailable (why, see above)) trip costs if( (cost of the current node + weight of the edge connecting them, with a neighbour) < (actual cost of reaching the neighbour, from the beginning node) ). When you changing unavailable to available, you must add changed elements to the priority queue. When you update a cost of node, you should upgrade heap, do not forget.

-Mark actually node as visited. Remove him from the priority queue (permanently, it's visited), in minimum-heap it's delete_root operation.

-Repeat until the queue isn't empty.

On your example it could look like this:

Number - actually the lowest total weight of path between nodes (first and last).

Stars - node is visited, this cost never changes.

Dash - node is not available in this moment.

| a | b | c | d |
-----------------
| 0 | - | - | - | <-- Available is only a.
-----------------
|*0*| 1 | 2 | - | <-- You can go to b and c.
-----------------
|*0*|*1*| 2 | 16| <-- b was cheaper, you updated costs from this vertex.
-----------------
|*0*|*1*|*2*| 3 | <-- You didn't stop, and find less costly way!
-----------------
|*0*|*1*|*2*|*3*| <-- Work done, the last vertex visited.
-----------------

More specifically, initially available is only first element, so at the beginning you must visit him. When it's done, available are two new nodes, and you should visit cheapest (from available, not visited). It's b. From b is the only way to d, so you upgrade only his cost (now d is available, but actual way (cost) may not be the optimal). Again take the cheapest vertex from available. It's c, because a and b are visited and 2 is smaller than 16. When you check this node you find better way to d, so you should update cost of d from 16 to 3. Visited last node (d) is formal and insignificant move. You visited all vertices, now your job is done.

Upvotes: 1

sgtHale
sgtHale

Reputation: 1547

If you want to speed up the algorithm, I suggest you implement the algorithm with binary heaps. Essentially what it does is it always tests the next lowest possible cost node with a very basic search.

http://algorithms.soc.srcf.net/notes/dijkstra_with_heaps.pdf

Upvotes: 0

Pradeep
Pradeep

Reputation: 126

In the first step the tentative distances of nodes from 'a' are found, which are s(b)= 1 and s(c) =2

Queue --> s(b) = 1, s(c) = 2

Now dequeing the priority queue we get b, so calculating tentative distances again s(d)= 16

Queue --> s(c) = 2, s(d) =16

Now dequeing we get c, so calculating tentative distances from c, s(d) =3 > previous value s(d)=17

So the shortest distance is 3

Upvotes: 1

twinlakes
twinlakes

Reputation: 10238

Every time the algorithm visits a node, it puts all its neighbors (that aren't visited already) into the priority queue. The priority queue keeps the elements sorted by least cost, so that the shortest distance is always calculated first.

So to answer your question, it goes from a->b, then a->c, then b->d, then c->d.

Upvotes: 0

Related Questions