Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Graph Theory- Shortest Path Algorithms
Transcript of Graph Theory- Shortest Path Algorithms
Processor operations mostly involve processing data. This data can be stored in memory and accessed from thereon. However, reading data from and storing data into memory slows down the processor, as it involves complicated processes of sending the data request across the control bus, and into the memory storage unit and getting the data through the same channel.
To speed up the processor operations, the processor includes some internal memory storage locations, called registers.
The registers stores data elements for processing without having to access the memory.
How to find the cost of the shortest path
between all pair of vertices in a weighted
Here we will apply dynamic programming.
DP consists of 4 steps:
1. Devise optimal substucture.
2.Recursively solve optimal substructure.
3. Get optimal solution.
4. Construct the optimal
Floyd Warshal Update Rule
Dij(k) Finding Rule
Computing π values
Initialize Source Node
These are mathematical structures used to model pairwise relations between objects. A gragh is made up of vertices and edges.
? Directed/Undirected Graphs
? Order of a graph
? Size of graph
? Weighted Edge
? π value
? Shortest Path
We use this algorithm when the objective
is to go from Point A (source) to
Point B (Sink), but there are multiple stops along the way.
Each stop is represented as a vertex and paths to each vertices are represented as edges of a specific length.
Dijkstra algorithm has multiple
applications in real life; mainly in
computer networking or commercial
How will we proceed?
We will draw two matrices namely D value matrix and π value matrix.
D value matrix holds the distance between the vertex i and j.
π value matrix holds the π value of path from i to j.
If the graph has n vertices, then both matrices will be of size nXn.
k will be our pivot element.
Relax (u, v, w)
If d[u] + w(u, v) < d[v]
then d[v] = d[u] + w[u, v]
for each v V do
d[v] ← ∞
π[v] ← NIL
d[s] ← 0
No. of vertices = 4
So our tables will have 4 rows and columns.
And we will iterate 4 times.
Define to be the shortest path from i to j such that any intermediate vertices
on the path are chosen from the
How to compute assuming that we have already computed the previous matrix
Case 1: Not going through k at all.
Case 2: Going through k
Jigyasa Meena Nikhil Raheja
Kiran Shori Sandeep Nemi
Meghna Shubham Singh
He will have his business offices
in New York, New Jersey, Vermont and Washington DC.
Also he will setting up his factory in one of the 4 cities mentioned.
Mr. Gru has a business of producing Jams and Jellies. He wants to extend his business over North East America.
Now our job is to help Mr. Gru find a location whose distance from other 3 cities is
From D4 matrix we can infer that the most suitable point to setup the factory would be vertex 2 i.e. Vermont
Content taken from lecture notes provided by
Wikipedia, Geeksforgeeks, Algohub.blogspot
Gru's images belongs to
(Finding Shortest Paths)
Dijkstra ain't perfect!
The algorithm fails with negative edge weights.
Even bigger problem exists with negative cycles.
BELLMAN FORD ALGORITHM
• To handle graphs with negative edge weights, we’ll need a new algorithm
• The Bellman-Ford algorithm is similar to Dijkstra’s but more robust.
• It will return the same output as Dijkstra’s for any graphs with only positive edge weights, but run slower
• Unlike Dijkstra’s, it correctly generates shortest paths in the presence of negative edge weights
• Very similar to Dijkstra’s except that instead of utilizing a priority queue to visit nodes in order, Bellman-Ford exhaustively iterates over every edge |V| times each, ensuring that all negative edge weights propagate.
• This strategy fixes the above example which Dijkstra failed for not evaluating the edges (A, B) and (B, C)
function BellmanFord(V, E, src):
for v in V:
v.dist = ∞
v.prev = null
src.dist = 0
repeat |V|-1 times:
for each edge (u,v) in E:
if u.dist + cost(u,v) < v.dist:
v.dist = u.dist + cost(u,v)
v.prev = u
//Relax edges repeatedly
A B C
Dr. Rinkaj Goel, GGSIPU