Dijkstra’s Algorithm: Project Report

Hafiz Saad Zia, Shafique Ahmed, Muhammad Waqas, Muhammad Maqsood

Department of Computer Science,

University of Agriculture, Faisalabad.

Dijkstra’s Algorithm is a graph search algorithm that solves the single-source shortest path problem for
a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used
in routing and other network related protocols.

1. Introduction
Dijkstra’s Algorithm was created in 1959 by the graph represent routers and edge path
Dutch computer scientist Edsger Dijkstra. costs represent data travel distances
While employed at the Mathematical Centre between pairs of routers connected by a
in Amsterdam, Dijkstra was asked to cable, Dijkstra's algorithm can be used to find
demonstrate the powers of ARMAC, a the shortest route between one router and
sophisticated computer system developed by all other routers.
the Mathematical Centre. Part of his
presentation involved illustrating the best Routing refers to the overall network-wide
way to travel between two points and in process that determines end-to-end paths
doing so, the shortest path algorithm was that datagram will take from source to
created. It was later renamed Dijkstra’s destinations. Each router has complete
Algorithm in recognition of its creator. information of the network, whereas in a
decentralized routing each router has a local
Dijkstra’s Algorithm is a graph search algorithm
view consisting of its directly attached
that solves the single-source shortest path
neighbors. For this we use Dijkstra’s
problem for a graph with nonnegative edge
Algorithm which is mostly preferred as it is
path costs, producing a shortest path tree. This
faster as compared to any other algorithm
algorithm is often used in routing and other
and its easy implementation.
network related protocols.

For a given source vertex (node) in the graph, Router-based information, which has been
the algorithm finds the path with lowest cost collected from other routers, builds a graph
(i.e. the shortest path) between that vertex of the network which shows the locations &
and every other vertex. It can also be used links of routers within themselves and in the
for finding costs of shortest paths from a network. These links are labeled with a
single vertex to a single destination vertex by number called weight or cost. If there are
stopping the algorithm once the shortest two links between a node and destination,
path to the destination vertex has been the router chooses the link with the lowest
determined. For example, if the vertices of weight.
 2. Algorithm forall vertices w in V – {1} do {no edges have
i. Read the number of nodes in a network been explored yet}
ii. Read the edge costs in the network among
the nodes. sDist[w]←∞
iii. Identify the source and destination
iv. Find the distance of each node from the end for;
source.
v. Select the node having the least weight. Fill New Frontier with vertices w in V organized
vi. Observe the node(s) that have been visited, by priorities sDist[w];
i.e. source node in this case.
vii. Find the distance of remaining nodes from endInitialize;
the selected node and repeat the previous
steps until the destination node is reached. repeat
viii. List the entire selected nodes from source
to destination in sequence in which they are v←DeleteMin{New FronƟer}; {v is the new
present in the graph to give the optimum closest; sDist[v] is already correct}
path.
forall of the neighbors w in Adj[v] do
3. Pseudo Code
The following pseudo-code gives a brief if sDist[w]>sDist[v] +EdgeCost(v,w) then
description of the working of the sDist[w]←sDist[v] +EdgeCost(v,w)
Dijkstra’s algorithm.
update w in New Frontier {with new priority
Procedure Dijsktra (V: set of vertices 1... n sDist[w]}
{Vertex 1 is the source}
endif

Adj[1…n] of adjacency lists; endfor

EdgeCost(u, w): edge – cost functions;) until New Frontier is empty

Var: sDist[1…n] of path costs from source endDijkstra;

(vertex 1);
{sDist[j] will be equal to The algorithm illustrates Best-First-Breadth-
the length of the shortest path to j} First-Search. It is the Best-First because the best
vertex is New Frontier is selected to be
Begin: processed next. The search used is Breadth-
First, since New Frontier consists of vertices
Initialize that can be tried next and these vertices are
one edge away from the explored vertices.
{Create a virtual set Frontier to store i where
sDist[i] is already fully solved} 4. Graphical Representation
Consider the following graph:
Create empty Priority Queue New Frontier; Where, routers represent nodes/vertices while
lines represent edges;
sDist[1]←0; {The distance to the source is zero} The numbers on edges are the edge
costs/weights.
4.1. Initial Step 4.4. Step 3
sDist[s]=0 ; the value to the source itself Computation from vertex b
sDist[a]= ∞, sDist[b]= ∞, Adj[b] = {d,e};
sDist[c]= ∞, sDist[d]= ∞ , sDist[d] > sDist[b]+ EdgeCost[b,d]
sDist[e]= ∞, sDist[t]= ∞; 13 > 4+7 (True)
The nodes not processed yet. Therefore, sDist[d]=11;
sDist[e]=10;

4.2. Step 1
Adj[s]={a,b,c}; computing the value of the 4.5. Step 4
adjacent vertices of the graph Computation from vertex c
sDist[a]=3; Adj[c] = {e};
sDist[b]=4; sDist[e] > sDist[c]+ EdgeCost[c,e]
sDist[c]=8; 10 > 8+5 (false)
Therefore, sDist[e]=10;

4.3. Step 2
Computation from vertex a 4.6. Step 5
Adj[a] = {d}; Adj[d] = {t};
sDist[d]=13; sDist[t]=16
4.7. Step 6
Computation from vertex e
Adj[e] = {t};
sDist[t] > sDist[e]+ EdgeCost[e,t]
16 > 10+3 (false)
Therefore, sDist[t]=13;

4.8. Resultant
This figure shows the final path obtained using
Dijkstra’s Algorithm.

5. Flow Chart
Since now, we have seen the main steps of
Dijkstra’s algorithm and got familiar with its Performance Parameters
pseudo code. We also have observed its
working on a given graph, in the graphical • Number of Hopes
represention section, described above. • Minimum Cost
• End-to-End delay
Now, we will take a look at the flow sheet • Throughput
diagram showing the main steps of Dijkstra’s • CPU processing at node
algorithm, in order to understand them • CPU memory requirement at node
properly:
 7. Disadvantages
The major disadvantage of the algorithm is the
Path
Set MC Hop E2E TP Proc. Mem fact that it does a blind search there by
consuming a lot of time waste of necessary
0 Ø 0 0 T1 O1 P1 M1
resources.
1 {s } 3 0 T2 O2 P2 M2
Another disadvantage is that it cannot handle
2 {s, a} 13 0 T3 O3 P3 M3
negative edges. This leads to acyclic graphs and
3 {s, a, b} 10 0 T4 O4 P4 M4 most often cannot obtain the right shortest
4 {s, a, b, c} 10 0 T5 O5 P5 M5 path.
5 { s, a, b, c,
16 1 T6 O6 P6 M6
d}
6 { s, a, b, c,
d, e}
13 1 T7 O7 P7 M7 8. Related Algorithms
7 { s, a, b, c,
13 2 T8 O8 P8 M8
• A* Algorithm is a graph/tree search
d, e, t}
∑
algorithm that finds a path from a given
Total 13 4 ∑T ∑P ∑M
O initial node to a given goal node It employs
a "heuristic estimate" h(x) that gives an
Where; estimate of the best route that goes
MC: Minimum cost; through that node. It visits the nodes in
Hop: Number of hops; order of this heuristic estimate. It follows
E2E: End-to-End Delay; the approach of best first search.
TP: Throughput;
Proc: Processing at node; • The Bellman–Ford Algorithm computes
Mem: Memory at node; single-source shortest paths in a weighted
digraph. It uses the same concept as that of
6. Efficiency Dijkstra’s algorithm but can handle negative
The complexity/efficiency can be expressed in edges as well. It has a better running time
terms of Big-O Notation. Big-O gives another than that of Dijkstra’s algorithm.
way of talking about the way input affects the
algorithm’s running time. It gives an upper • Prim’s Algorithm finds a minimum spanning
bound of the running time. tree for a connected weighted graph. It
In Dijkstra’s algorithm, the efficiency varies implies that it finds a subset of edges that
depending on |V|=n DeleteMins form a tree where the total weight of all the
and |E| updates for priority queues that were edges in the tree is minimized. it is
used. sometimes called the DJP algorithm or
If a Fibonacci heap was used then the Jarnik algorithm.
complexity is O( | E | + | V | log | V | ) ,
whichis the best bound. The DeleteMins 9. Applications
operation takes O(log|V|). Traffic information systems use Dijkstra’s
If a standard binary heap is used then the algorithm in order to track the source and
complexity is O( | E |log |E|),| E | destinations from a given particular source and
Log|E| term comes from|E|updates for the destination
standard heap.
If the set used is a priority queue then the OSPF- Open Shortest Path First, used in Internet
complexity is O(|E|+|V|2). O(V|2) routing. It uses a link-state in the individual
Term comes from |V| scans of the unordered areas that make up the hierarchy. The
set New Frontier to find the vertex with the computation is based on Dijkstra's algorithm
least sDist value. which is used to calculate the shortest path tree
inside each area of the network.