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(*n*^{2} + *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(*m*^{2}) 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(*n*^{2}). The total cost for
finding the center is O(*m* + *n*^{2}).

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.