Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start 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

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Graph Theory- Shortest Path Algorithms

No description
by

Nikhil Raheja

on 30 October 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Graph Theory- Shortest Path Algorithms

Graph
theory

Dijkstra
Algorithm
Floyd WarshalL
Algorithm
Introduction
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
directed graph.


Here we will apply dynamic programming.
DP consists of 4 steps:
1. Devise optimal substucture.
2.Recursively solve optimal substructure.
(bottom-up manner)
3. Get optimal solution.
4. Construct the optimal
solution.
Formulation

Floyd Warshal Update Rule
Dij(k) Finding Rule
Computing π values
Example
Relaxation Procedure
Initialize Source Node
Dijkstra Algorithm
? Graphs
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
shipping.
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]
}

INIT(G, s)
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
set {1,2,3..k}
How to compute assuming that we have already computed the previous matrix
Case 1: Not going through k at all.
Consider
Case 2: Going through k
Consider
Thank you!
Jigyasa Meena Nikhil Raheja
Kiran Shori Sandeep Nemi
Meghna Shubham Singh

Efforts by:
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
minimum.

Problem
Solution
printpath(π,i,j)
{
if (i==j)
print i;
else
printpath(π,i,π );
print j;
}

ij
From D4 matrix we can infer that the most suitable point to setup the factory would be vertex 2 i.e. Vermont
Result:
Websites Refered
Content taken from lecture notes provided by
Wikipedia, Geeksforgeeks, Algohub.blogspot

Gru's images belongs to
Illumination Entertainment
(Finding Shortest Paths)
Dijkstra ain't perfect!
The algorithm fails with negative edge weights.
Even bigger problem exists with negative cycles.
Currency Arbitrage
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

PseudoCode
//Relax edges repeatedly
C
D
E
B
D
E
B
10
5
9
5
Q:
A B C

D
E
10
5
9
5
7
Dr. Rinkaj Goel, GGSIPU
Full transcript