KEMBAR78
Shortest Paths Algorithms - I | PDF | Combinatorics | Applied Mathematics
Scribd
Upload
139 views22 pages

Shortest Paths Algorithms - I

The document discusses algorithms for finding the shortest path between two vertices (nodes) in a graph. It first discusses Dijkstra's algorithm for finding shortest paths in weighted directed graphs. However, Dijkstra's algorithm does not work for graphs with negative edge weights, as the shortest path could traverse a negative cost cycle. The document then introduces the Bellman-Ford algorithm, which can handle graphs with negative edge weights by detecting negative cost cycles. It provides an example application of Bellman-Ford and notes that detecting a negative cost cycle is possible using Bellman-Ford by checking for a distance decrease on the final iteration.

Uploaded by

Aaryan S Verma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
139 views22 pages

Shortest Paths Algorithms - I

The document discusses algorithms for finding the shortest path between two vertices (nodes) in a graph. It first discusses Dijkstra's algorithm for finding shortest paths in weighted directed graphs. However, Dijkstra's algorithm does not work for graphs with negative edge weights, as the shortest path could traverse a negative cost cycle. The document then introduces the Bellman-Ford algorithm, which can handle graphs with negative edge weights by detecting negative cost cycles. It provides an example application of Bellman-Ford and notes that detecting a negative cost cycle is possible using Bellman-Ford by checking for a distance decrease on the final iteration.

Uploaded by

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

Shortest Paths

Algorithms - I
- Shashank Dargar
The problem which we will discuss today:
Suppose we are given a weighted directed graph G = (V, E, w) with two special
vertices, and we want to find the shortest path from a source vertex s to a target
vertex t. That is, we want to find the directed path P starting at s and ending at t
that minimizes the function

Or, Suppose you want to drive from city A to city B and you want to find the
shortest path that you should take.
The problem which we will discuss today:
Suppose we are given a weighted directed graph G = (V, E, w) with two special
vertices, and we want to find the shortest path from a source vertex s to a target
vertex t. That is, we want to find the directed path P starting at s and ending at t
that minimizes the function

Or, Suppose you want to drive from city A to city B and you want to find the
shortest path that you should take.

What if the graph is undirected and unweighted??


What if the graph is undirected and unweighted??
What if the graph is undirected and unweighted??

A simple BFS should do. ;)


Bfs works for all graphs which are unweighted (Both directed and undirected)
Now let’s come back to directed and weighted graph,
Consider the graph given below,
We can use Dijkstra’s algorithm….
We can use Dijkstra’s algorithm….
We can use Dijkstra’s algorithm….
Will Dijkstra always work ??
Will Dijkstra always work ??
Consider a graph with negative weights.

Unfortunately, when the input graph has negative edges, the same vertex can be
extracted multiple times; the same edge can be relaxed multiple times; and
distances might not be discovered in increasing order.
Dijkstra runs into infinite loop if the graph contains negative cycle (The what?? )
Towards a better algorithm, Bellman Ford
Bellman ford was the first Dynamic programming algorithm developed.

It uses number of edges as an additional parameter to keep track of the repetitions


in Dijkstra.

The DP recurrence for Bellman ford is:


Bellman Ford algorithm
Shortest path from s -> d, can have a length of atmost n-1. (Why?)

If Shortest path from s to u comprises of a, b, c and d, then it will be the shortest


path to a, b, c and d too.
Bellman Ford algorithm
We compute iteratively all shortest paths to vertex i, consisting of atmost e edges,
the values of e range from 0 to n-1.

First calculate shortest path to each vertex using atmost 1 edge ( inf if
unreachable)

Then using the obtained result, calculate shortest path to each vertex using atmost
2 edges.

Then using 3 edges and so on, till n-1 edges in total.


Towards a better algorithm, Bellman Ford
The DP recurrence for Bellman ford is:
Example of Bellman ford
Example of Bellman ford
Example of Bellman ford
How will you detect a negative cycle in a connected
weighted graph??
Hint: Think something using Bellman ford
Some problems for practice:
https://www.e-olymp.com/en/problems/1453

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=sh
ow_problem&problem=364

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category
=12&page=show_problem&problem=1040

You might also like