Scribd
Upload
59 views20 pages

Dijsktra Algo

The document discusses Dijkstra's algorithm, which finds the shortest paths between vertices in a graph. It provides an overview of the single-source shortest path problem, describes how Dijkstra's algorithm works using a greedy approach, and gives pseudocode and analysis of its running time.

Uploaded by

Faiza Rasheed
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
59 views20 pages

Dijsktra Algo

The document discusses Dijkstra's algorithm, which finds the shortest paths between vertices in a graph. It provides an overview of the single-source shortest path problem, describes how Dijkstra's algorithm works using a greedy approach, and gives pseudocode and analysis of its running time.

Uploaded by

Faiza Rasheed
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 20

DIJKSTRA'S ALGORITHM

SINGLE-SOURCE SHORTEST PATH PROBLEM

Single-Source Shortest Path Problem - The problem of


finding shortest paths from a source vertex v to all other
vertices in the graph.
DIJKSTRA'S ALGORITHM
Dijkstra's algorithm - is a solution to the single-source
shortest path problem in graph theory.

Works on both directed and undirected graphs. However, all


edges must have nonnegative weights.

Approach: Greedy

Input: Weighted graph G={E,V} and source vertex v∈V, such


that all edge weights are nonnegative

Output: Lengths of shortest paths (or the shortest paths


themselves) from a given source vertex v∈V to all other
vertices
DIJKSTRA'S ALGORITHM - PSEUDOCODE

dist[s] ←0 (distance to source vertex is zero)


for all v ∈ V–{s}
do dist[v] ←∞ (set all other distances to infinity)
S←∅ (S, the set of visited vertices is initially empty)
Q←V (Q, the queue initially contains all vertices)
while Q ≠∅ (while the queue is not empty)
do u ← mindistance(Q,dist) (select the element of Q with the min. distance)
S←S∪{u} (add u to list of visited vertices)
for all v ∈ neighbors[u]
do if dist[v] > dist[u] + w(u, v) (if new shortest path found)
then d[v] ←d[u] + w(u, v) (set new value of shortest path)
(if desired, add traceback code)
return dist
SPANNING TREE
 The Spanning Tree Protocol (STP) is a network
protocol that ensures a loop-free topology for
Ethernet networks. The basic function of STP is
to prevent bridge loops and the broadcast
radiation that results from them.
 A minimum spanning tree is a spanning
tree of a connected graph. It connects all the
vertices together with the minimal total
weighting for its edges. A single graph can have
many different spanning trees.
DIJKSTRA ANIMATED EXAMPLE
DIJKSTRA ANIMATED EXAMPLE
DIJKSTRA ANIMATED EXAMPLE
DIJKSTRA ANIMATED EXAMPLE
DIJKSTRA ANIMATED EXAMPLE
DIJKSTRA ANIMATED EXAMPLE
DIJKSTRA ANIMATED EXAMPLE
DIJKSTRA ANIMATED EXAMPLE
DIJKSTRA ANIMATED EXAMPLE
DIJKSTRA ANIMATED EXAMPLE
IMPLEMENTATIONS AND RUNNING TIMES
The simplest implementation is to store vertices in an array
or linked list. This will produce a running time of

O(|V|^2 + |E|)

For sparse graphs, or graphs with very few edges and many
nodes, it can be implemented more efficiently storing the
graph in an adjacency list using a binary heap or priority
queue. This will produce a running time of

O((|E|+|V|) log |V|)


DIJKSTRA'S ALGORITHM - WHY IT WORKS

 As with all greedy algorithms, we need to make sure that it


is a correct algorithm (e.g., it always returns the right solution
if it is given correct input).

A formal proof would take longer than this presentation, but


we can understand how the argument works intuitively.

 If you can’t sleep unless you see a proof, see the second
reference or ask us where you can find it.
DIJKSTRA'S ALGORITHM - WHY IT WORKS
 To understand how it works, we’ll go over the
previous example again. However, we need two
mathematical results first:

 Lemma 1: Triangle inequality


If δ(u,v) is the shortest path length between u and v,
δ(u,v) ≤ δ(u,x) + δ(x,v)
 Lemma 2:
The subpath of any shortest path is itself a shortest
path.

 The key is to understand why we can claim that anytime we


put a new vertex in S, we can say that we already know the
shortest path to it.
 Now, back to the example…
DIJKSTRA'S ALGORITHM - WHY USE IT?

 As mentioned, Dijkstra’s algorithm calculates


the shortest path to every vertex.
 However, it is about as computationally
expensive to calculate the shortest path from
vertex u to every vertex using Dijkstra’s as it is
to calculate the shortest path to some particular
vertex v.
 Therefore, anytime we want to know the optimal
path to some other vertex from a determined
origin, we can use Dijkstra’s algorithm.
APPLICATIONS OF DIJKSTRA'S ALGORITHM
- Traffic Information Systems are most prominent use
- Mapping (Map Quest, Google Maps)
- Routing Systems

You might also like