CODEWITHSUNDEEP
c++algorithmdijkstra
Damerian
Damerian

Reputation: 59

Dijkstra's Algorithm and the greedy strategy

I seem to be having a bit of trouble understanding how the greedy strategy works and how Dijkstra's Algorithm keeps track of the shortest path. For reference, here is the pseudo code for Dijkstra's Algorithm

DijkstrasAlgorithm(G, w, s)
    InitalizeSingleSource(G, s)
    S = 0
    Q = G.V
    while Q != 0
        u = ExtractMin(Q)
        S = S∪{u}
        for each vertex v ∈ G.Adj[u]
            Relax(u, v, w)

Please consider the following weight direction graph.

There are 5 vertices: s, t, x, y, z There are 10 edges: 

s->t = 3
s->y = 5
t->y = 2
t->x = 6
y->t = 1
y->x = 4
y->z = 6
x->z = 2
z->x = 7
z->s = 3

Our goal is to find the shortest path from s to x. My answer was s->t->y->x with length 9, I assumed that "S" in the pseudo code was the shortest path and that each ExtractMin from minQ was added onto the path.

My teacher, however, has told me that this is wrong. The correct answer is s->t->x with length 9. The difference in our answer is whether to include y. My teacher says that since s->t->x is "found first", it is not updated to s->t->y->x, which is of equal length.

This confuses me. Dijkstra's Algorithm uses the greedy strategy, and I thought the greedy strategy was to always pick the shortest path available at the time. And when the the choice is between t->y and t->x, t->y is shorter and should therefore be picked.

My questions are:

1) In what circumstances will the greedy strategy not pick the immediate shortest path for the end result?

2) If using ExtractMin on minQ isn't how we keep track of the overall path from s to x, then how do we keep track of the full path?

Upvotes: 0

Views: 559

Answers (1)

btilly
btilly

Reputation: 46408

Your teacher's answer assumes that we explore paths in the order, "shortest first, broken by first seen first".

To start with we explore s->t we put x at cost 9 from s->t->x onto the list of things to explore 'some day'. But we first explore s->t->y because it is shorter. At that point, we see that s->t->y->x is an option, also of cost 9. However because this is not an improvement we drop it.

Therefore once we get to paths of length 9, we find s->t->x out because it went on the queue first.

You would get your answer out if you modified Relax to save a possible path if it is better than or equal to the best so far found. This would get a correct answer.

As for how the path is extracted from the end, each node knows how you get to it. So start from the end and follow the cookie trail backwards to find the path in reverse, then reverse it to get the actual path.

Upvotes: 2

Related Questions