Dijkstra’s algorithm is one of the most useful graph algorithms. The algorithm can be modified to solve many different problems.
Dijkstra’s is greedy algorithm for the shortest distance from a start vertex to every other vertex in a weighted graph.
Algorithm: ShortestPath(G, v) // a little miss leading since the output is only the distance
input: A simple undirected weighted graph G
with non negative edge weights and a start vertex, v.
output: D(u) the distance u is from v.
Initialize D(v)
= 0 and D(u) = ∞
for u != v
Initialize priority queue Q of
vertices using D as key.
while Q is not empty do
u = Q.removeMin()
for each vertex z adjacent to u
and in Q do
if D(u) + w((u, z)) < D(z) then
D(z) = D(u) + w((u, z))
update z in Q
return D
Dijkstra’s uses:
· Weighted graph
· Distance function or array
· Priority Queue
· Relaxation
The cost is:
O((n+m) lg n) using a heap
O(n2 + m) using an unsorted sequence
All of Dijkstra’s component can be modified to solve different problems.
· Graph – the vertices, edges and edge weight can have different meanings.
· Distance – the distance can have different meaning. Also the distance of a path can be changed.
· Priority Queue – The priority queue can have different comparison relation. For example the priority queue can be min or maximum.
· Relaxation and Distance Initialization – the relaxation process can be different and require a different distance initialization.
The modification to Dijkstra’s algorithm is best illustrated with an example.
In a telephone network the lines have bandwidth, BW. We want to route the phone call via the highest BW.
The bandwidth of a transmission line is the highest frequency that can be supported by the line. Generally, the higher the frequency of the signal the more the signal is attenuated by the line. If we are transmitted a digital signal then the BW represents the highest frequency or the fastest the signal can change from 0 to 0. Bandwidth represents the amount of information that can transmitted by the line.
What graph should we use for this problem?
The vertices represents switching station, the edges represents the transmission line, and the weight of edges represents the BW.
What is the distance function?
The distance function is the BW of the path with the max BW for the route.
What is the BW of a path or route, P?
BW(P) = min{BW(e) | edge, e, of P}, the weakest link.
What priority queue should we use?
We want the highest BW so a max PQ.
How should BW be initialized for each vertex? What is the BW of the vertex with itself?
The BW of the vertex with itself is infinite. So we should initialize the BW by
BW(v) = inf, v the start vertex.
BW(u) = 0 for u ≠ v
What is the relaxation?
if min(BW(u, z), BW(u) ) > BW(z) then BW(z) = min(BW(u, z), BW(u))
What does the above mean?
So we can but it all together
Algorithm: HighestBW(G, v)
Initialize BW(v)
= ∞ and BW(u) = 0 for u != v
Initialize priority queue Q of vertices using BW as key.
while Q is not empty do
u = Q.removeMax()
for each vertex z adjacent to u
and in Q do
if min(BW(u, z), BW(u) ) > BW(z) then
BW(z) = min(BW(u, z), BW(u) )
update z in Q
return
BW
Cost?
The best route?
A travel agent requests software for making an agenda of flights for clients. The agent has access to a data base with all airports and flights. Besides the flight number, origin airport and destination, the flights have departure and arrival time. Specifically the agent wants to determine the earliest arrival time for the destination given an origin airport and start time.
Let’s try to modify Dijkstra’s algorithm.
The graph is a di-graph
vertices are airports and
di-edges are flights with two weights, departure time, departT and arrival time, arriveT.
Distance function should be earliest arrival time, T, at the airports.
The arrival time of a sequence of flights is the arrival time at the destination airport, i.e. last flight.
We still use a “minimum” priority queue, Q, of airports keyed by T.
But the arrival time at the start vertex (i.e. origin airport), s, T[s] = startT, start time.
The adjacent loop must be modified:
· Can only select fights, f, that can be caught, i.e. f.departT ≥ T[v]
· Also want fight with the minimum arrival time.
How can we determine the best connecting flight? Make another priority queue, P:
for all vertices, w, adjacent to v do
make Priority Queue, P, of fights, f, with f.departT ≥ T[v]
keyed by f.arriveT
Time t ← ∞ // will need for relaxation
if P is not empty then t ← P.min().arriveT // no need to remove
Relaxation is nearly the same
if t < T[w] then
T[w] ← t
update w in Q
But it all together:
FlightAgenda(DiGraph G, Vertex s, Time startT)
// Input: G di-graph, not a simple graph
// vertices are airports
// di-edges are flights with two weights
// departT is the departure time at origin airport
// arriveT is the arrival time at the destination airport
// s is the origin airport and startT is the starting time
// initialize arrival time, T
T[s] ← startT
for all vertex, v ≠ s do T[v] ← ∞
make Priority Queue, Q, of vertices keyed by T
while Q is not empty do
v ← Q.removeMin()
for all vertices, w, adjacent to v and in Q do
// determine the next flight
make Priority Queue, P, of fights, f, with f.departT ≥ T[v]
keyed by f.arriveT
Time t ← ∞
if P is not empty then t ← P.min().arriveT // no need to remove
// relaxation
if t < T[w] then
T[w] ← t
update w in Q
return T
What is the cost?
Determining the cost is difficult because of the additional cost of making all the flight priority queues. We might assume that in the worst case m flight priority queues are made at O(m) cost to construct each priority queue. So a total cost O(m2) for making all the flight priority queues. This is a definitely an excessively large upper bounds. The reason is because in worst case there would not m priority queues each with m flights. Another way to consider is the counting is that each edge is but into only one flight priority queue. Then the total cost for constructing all the flight priority queues is O(m), if the algorithm is implemented properly. The total cost using a heap for the airport priority queue is O((n + m) lg n)
Again the complete agenda can be determined by back calculating the route from the destination airport or using additional data structure, a map, which keep where the updates were made from.
We want to designate a file server in a local area network. Now, we consider that most of time transmitting files from one computer to another computer is the connect time. So we want to minimize the number of “hops” from the file server to every other computer on the network.
In other words we want to find the center of the network. We do not use Dijkstra’s algorithm.
An easier problem is to assume that the network is a free tree.
Any ideas how to find the center of the tree?
What vertices definitely are not the center of the tree? The leaves of the tree.
So we should remove all the leaves.
The algorithm is iteratively remove the leaves form the tree.
Is the center unique? No, there could be two, both are good.
Back to the bigger problem, how can we make a tree form a network? A graph traversal.
Which graph traversal is best? Breath first search, because the spanning trees are bushier than a depth first search.
Does it matter where we start the graph traversal? No. None the start vertex could be a leaf in the free tree.
What is the cost?
The cost of making the spanning tree is O(n + m). In the worst case the spanning tree will have to be pruned n/2 times. Then the total cost for pruning all the trees is O(n2). The total cost for finding the center is O(m + n2).
There is alternative algorithm. Perform breath first search on each vertex and keep track of the vertex with the minimum number of levels. The cost of this algorithm is O(n(m + n)) larger than the previous algorithm.