**Graph**

theory

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