[go: up one dir, main page]
Scribd
Upload
39 views6 pages

Graph - Shortest Path From Algorithm Algorithm: P Vasuki

This document describes the Bellman-Ford algorithm for finding the shortest paths from a source vertex to all other vertices in a graph. It initializes all distances as infinite except the source which is 0. It then iterates through the edges |V|-1 times, updating distances if a shorter path is found. After this, it checks for a negative weight cycle by iterating through the edges one more time and checking for any distances that can still be decreased, which would indicate a negative cycle.

Uploaded by

sudhan
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
39 views6 pages

Graph - Shortest Path From Algorithm Algorithm: P Vasuki

This document describes the Bellman-Ford algorithm for finding the shortest paths from a source vertex to all other vertices in a graph. It initializes all distances as infinite except the source which is 0. It then iterates through the edges |V|-1 times, updating distances if a shorter path is found. After this, it checks for a negative weight cycle by iterating through the edges one more time and checking for any distances that can still be decreased, which would indicate a negative cycle.

Uploaded by

sudhan
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/ 6

Graph – Shortest Path from

Algorithm

P VASUKI
Bellman Ford Algorithm
• nput: Graph and a source vertex src
Output: Shortest distance to all vertices from src. If there is a
negative weight cycle, then shortest distances are not calculated,
negative weight cycle is reported.
Bellman Ford Algorithm
• 1) This step initializes distances from source
to all vertices as infinite and distance to source
itself as 0. Create an array dist[] of size |V|
with all values as infinite except dist[src]
where src is source vertex.

• 2) This step calculates shortest distances. Do


following |V|-1 times where |V| is the number
of vertices in given graph.
a) Do following for each edge u-v
If dist[v] > dist[u] + weight of edge uv,
then update dist[v]
dist[v] = dist[u] + weight of edge uv
Algorithm contd…
• 3) This step reports if there is a negative weight
cycle in graph. Do following for each edge u-v

• If dist[v] > dist[u] + weight of edge uv, then


“Graph contains negative weight cycle”
The idea of step 3 is, step 2 guarantees shortest
distances if graph doesn’t contain negative
weight cycle. If we iterate through all edges one
more time and get a shorter path for any vertex,
then there is a negative weight cycle
Example

• On Board ..
Additional Reference - Visualization

• https://visualgo.net/en/sssp

You might also like