Scribd
Upload
12 views

Dijkstra's Algorithm Example W22

The document provides instructions for using Dijkstra's algorithm to find the shortest path between two vertices in a graph. It explains the key rules: (1) add vertices with the shortest distance to the starting vertex not already in the solution set S; (2) distances can only decrease as you explore paths through vertices in S. An example applies these rules in 5 steps to find the shortest path from vertex a to f, with intermediate vertices added to S and distance updates shown in a table.

Uploaded by

jumpman006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views

Dijkstra's Algorithm Example W22

The document provides instructions for using Dijkstra's algorithm to find the shortest path between two vertices in a graph. It explains the key rules: (1) add vertices with the shortest distance to the starting vertex not already in the solution set S; (2) distances can only decrease as you explore paths through vertices in S. An example applies these rules in 5 steps to find the shortest path from vertex a to f, with intermediate vertices added to S and distance updates shown in a table.

Uploaded by

jumpman006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

As you get to the homework for week 10, you'll notice we are looking for a table format with

your
answers.

Remember we have a couple of rules for Djikstra:

In each step, we add a single vertex to the set S. This vertex must be a vertex of the least
distance to the starting vertex that isn't already in S.

When computing the distance, we want the shortest distance from the start to the given vertex,
but we are only allowed to go through the vertices in S to get there.

There are some "shortcut" rules that are consequences of the two rules above:

Once you add a vertex to S, the distance for that vertex is now fixed and cannot change.

If you come upon a tie (two vertices with the same distance), you can add either one to the
graph.

You do not get to add the destination vertex when you first change it from infinity. You have to
wait until it is the next logical vertex to add to S. This is because you might get a shorter path
later.

As you move along through the steps, the distances never increase, only decrease!

Let's look at this example: Find the shortest path from vertex a to f.
First, we can set up our table with columns for Step #, the current state of the solution set S,
and the current state of the solution for each vertex.

Step 0:

We are currently at our starting vertex a and so our distance for L(a) is 0, and all other columns
are ∞.

Step 1:

So to start, we need to add a to our solution set S, which now allows us to see adjacent vertices
to a and their distances. We update our table columns for these vertices to account for the
distance and the vertices used to find the solution for each vertex.

Step 2:

We now choose a vertex that is not yet in the solution set S that also has the smallest distance
available to us. We see vertex b and e both have a distance of 3. We can choose either of them!
For this example, vertex b was chosen.

We can now include b in the set S and update b's column to include b. Also, we know that
columns L(a) and L(b) are fixed in their distances and will not change. Now, because we have
vertex b in our solution set S, we can see all adjacent vertices to b (c and e), and so we can
update the current distance and solution to c because the distance to c through b is less than
infinity. The current distance for c = 10 because we have the distance to b (3) + the distance to c
(7).

Notice that we also can "see" the adjacent vertex e when including vertex b in the solution set S.
However, the path to e through b is at a greater distance than what we already can achieve by a
-> e, and so we do not update e.

Step 3:

So now what do we add to the solution set S? We add e, because e has the current shortest
distance (3) compared to the other vertices that have not already been included in the solution
set S. And so we update our column for L(e) and include e in the solution to finding the shortest
path to e. Now, L(a), L(b), and L(e) are locked in, and we cannot change their
distances/solutions.

Adding vertex e to the solution set allows us to see the adjacent vertices d, f, c, and g. For c and
g, the new path through c is at a longer distance than what they currently are in the table, and
so we do not update their columns. For d and f, we calculate their distances and add their
solution paths. The distance to d = 14, because we add the distance to e plus the distance to d
(3 + 11 = 14). The distance to f = 7, because we add the distance to e plus the distance to f (3 +
4 = 7).

Step 4:

You may want to add vertex f to the solution set S next...but that would not be correct. Instead,
we need to choose the vertex with the current shortest distance, which would be g. We update
the column for L(g) and it is now locked in and cannot change.

We can now "see" the adjacent vertices to g, which are a, e, and f. Both a and e are already
"locked in" and cannot change. However, notice that taking the path through g to the vertex f is
of a shorter distance than what we had previously. So we update the column for L(f) to reflect
the shortest distance and path through g.

Step 5:

So what are our options here? We can see that the vertex with the shortest distance is now
f....which is the vertex we wanted to get to!

So we update the solution path for column L(f) and fill in the other columns with their values
from above.
Because we have found the goal vertex, we have our answer and can stop the algorithm. We
can see our solution in the last row for column L(f).

a->f: Distance of 5 by going a->g->f.

Credit: Ben Wichser and Ryan Adams.

You might also like