Network Optimization(1): Shortest Path Problem
Before I introduce the topic, let’s think for a minute the following questions.
- How do you decide which train to ride when there are several available?
- Have you ever thought about how GoogleMap comes up with the best route suggestion when you search for direction to anyplace?
Problems such as finding the shortest route from one place to another, choosing a moving direction where people can escape as many as possible in a disaster, etc, can be categorized as network optimization problems. There are other applications besides the traffic management fields, for example, how to transfer data efficiently (fewer delays) in telecommunication fields.
Today I will introduce one problem from network optimization and algorithm used to solve it.
Network Diagram: Graphs
Interconnection between entities is commonly represented by a network diagram which is known as Graphs. It is constructed by nodes (vertice), represent the entities, and arcs (edges), represent the connections. For example, in the maps (Figure from Google Maps) shown above, each city is a node and the connection route between two cities is an arc. In some cases, we also can add weights to edges (for example to represent the distance between two cities or time consumed moving between two places).
To handle a problem using graphs on a computer, an adjacency matrix is used. Each row and column corresponded with a node. We put 1 in row i — column j if there is an arc between node i and node j, otherwise we put 0. In case we want to work with weights information, 1 can be replaced by each edge’s weight.
Shortest Path Problem
Shortest Path Problem is one of network optimization problems that aims to define the shortest path from one node to another. For example, with the following graphs, suppose we want to find the shortest path from node1 to node6. Here values on edges are lengths between nodes. In this case, the red path is the shortest one with length 8.
Dijkstra’s Algorithm
Now let me introduce an efficient algorithm to solve the shortest path problem: Dijkstra’s Algorithm.
As preparation, we define some necessary elements as follow:
- Set L: store nodes whose shortest path from the start node is finalized.
At the initial state, L is an empty set - Set N: store nodes whose shortest path from the start node is not yet finalized.
At the initial state, N is a set of all nodes in the graphs - List d: store temporary length from the start node to each node.
d(i): temporary length from the start node to node-i
At the initial state, d(start)=0 and d(i)=∞ - List l: label showing the previous node before reaching a node using the shortest path
l(i): in the shortest path, a node before node-i is node-l(i)
Step1
From N, choose a node-i whose d(i) is the minimum value of list d. Then, remove node-i from N and insert it into L. In our example, node-1 is selected and update N and L to N={2,3,4,5,6}, L={1}. Next, for every node which can be reached from node-i, update its d and l values with information from the original graphs. In our case, from node-1 we can directly reach node-2,3,4, so d(2)=∞→2(length from node-1), l(2)=1(to reach node-2 we move from node-1); d(3)=∞→8, l(3)=1; d(4)=7, l(4)=1
==============================
remove node1 from N and insert into L ̤
N : {2, 3, 4, 5, 6}
L : {1}
d : [0, 2, 8, 7, inf, inf]
l : [0, 1, 1, 1, 0, 0]
==============================
Step2
From N, node-2 has d(2)=2 which is the smallest value. We remove node-2 and insert it into L. Next, update d and l value of every node which can be reached from node-2. For i≠2, update d(i) if and only if d(i)>d(2)+length(2,i) , meaning change d(i) value only the case moving from the latest selected node has shorter length compared to it current d(i). In this case, d(3)=8 >d(2)+4=6, so we update d(3)=6 and l(3)=2(shorter length moving from node-2). However, d(7)=7<d(2)+6=8, in this case we do not update the d(4),l(4) value. For d(5), since ∞>d(2)+5=7, so d(5)=7, l(5)=2.
==============================
remove node2 from N and insert into L ̤
N : {3, 4, 5, 6}
L : {1, 2}
d : [0, 2, 6, 7, 7, inf]
l : [0, 1, 2, 1, 2, 0]
==============================
Repeat this process until the goal node is added into L.
Step3
From N, node-3 has d(3)=6 which is the smallest value. We remove node-3 and insert it into L. Next, update d and l value of every node which can be reached from node-3 as we did in step2.
==============================
remove node3 from N and insert into L ̤
N : {4, 5, 6}
L : {1, 2, 3}
d : [0, 2, 6, 7, 7, inf]
l : [0, 1, 2, 1, 2, 0]
==============================
Step4, Step5
==============================
remove node4 from N and insert into L ̤
N : {5, 6}
L : {1, 2, 3, 4}
d : [0, 2, 6, 7, 7, 10]
l : [0, 1, 2, 1, 2, 4]
==============================
remove node5 from N and insert into L ̤
N : {6}
L : {1, 2, 3, 4, 5}
d : [0, 2, 6, 7, 7, 8]
l : [0, 1, 2, 1, 2, 5]
==============================
Step6
Now, only node-6 remained in N. Moving node-6 from N to S and we finish.
==============================
remove node6 from N and insert into L ̤
N : set( )
L : {1, 2, 3, 4, 5, 6}
d : [0, 2, 6, 7, 7, 8]
l : [0, 1, 2, 1, 2, 5]
==============================
As a result, the shortest path from node1 to node6 is
Goal:node6 ← l(6)=node5 ← l(5)=node2 ← l(2)=node1:Start
