In this video, I'll talk about how to solve the shortest path problem using Dijkstra's
algorithm for undirected networks.
We assume that each arc in the network has a length associated with it.
Suppose we start at a particular node.
The problem of finding the shortest path (or the path with the minimum length) from this
node to any other node in the network is called a shortest path problem.
If arc (i, j) is on the shortest path, we can denote it with xij=1.
Otherwise, xij=0.
Now let's see an example.
This is an undirected network.
It has 6 nodes and 9 arcs.
Suppose we want to find the shortest path from node A to node D.
The first step is to mark every node with a distance of positive infinity.
Now, let's start with node A. Let's update the distance.
From node A to itself, the shortest length is 0.
Now, let's check its neighbors.
Node A has two direct neighbors, node B and node F.
The distance from A to B is 0+2=2, which is smaller than positive infinity, so we replace
it with 2.
The distance from A to F is 0+3=3, which is smaller than positive infinity, so we replace
it with 3.
Now out of all the unvisited nodes, node B has the shortest distance.
So we move from A to B. Now, let's check the neighbors of the visited
nodes.
Node B has two direct neighbors, node C and node F.
Let's update the distance of node C. It is 2+6=8, which is smaller than positive infinity,
so we replace it with 8.
Let's update the distance of node F. It is 2+1=3, which is the same as the previous value,
so we leave it at 3.
Now out of all the unvisited nodes, node F has the shortest distance.
We have two options, either move from B to F or from A to F. It means the problem may
have multiple shortest paths.
I just randomly choose to move from B to F. Now, let's check the neighbors of the visited
nodes.
Node F has two direct neighbors, node C and node E.
Let's update the distance of node C. It is 3+4=7, which is smaller than the old value
8, so we replace it with 7.
Let's update the distance of node E. It is 3+7=10, which is smaller than positive infinity,
so we replace it with 10.
Now out of all the unvisited nodes, node C has the shortest distance.
We move from F to C. Node C has two direct neighbors, node D and
node E. Let's update the distance of node D. It is
7+8=15, which is smaller than positive infinity, so we replace it with 15.
Let's update the distance of node E. It is 7+3=10, which is the same as the previous
value, so we leave it at 10.
Now out of all the unvisited nodes, node E has the shortest distance.
We have two options, either move from C to E or from F to E. Again, it means the problem
may have multiple shortest paths.
I just randomly choose to move from C to E. Now, let's check the neighbors of the visited
nodes.
Node E has just one direct neighbor, node D.
Let's update the distance of node D. It is 10+4=14, which is smaller than the old value
15, so we replace it with 14.
Now node D is the only unvisited node.
We move from E to D.
The shortest path from A to D is ABFCED.
The distance is 14.
This is just one of the shortest paths.
We can use this algorithm to find other shortest paths.
For example, ABFED, and AFED, and AFCED.
They all have a distance of 14.
Okay, that is how to solve the shortest path problem using Dijkstra's algorithm for undirected
networks.
Thanks for watching.