[go: up one dir, main page]
Scribd
Upload
9 views14 pages

Data Structure

The document presents the Bellman-Ford Algorithm, which finds the shortest path from a single source to all vertices in a weighted graph, accommodating negative weight edges. It outlines the algorithm's steps, including initialization, edge relaxation, and negative cycle detection, and provides a practical scenario involving a flight booking system. The conclusion emphasizes the algorithm's effectiveness and flexibility in handling various graph conditions.

Uploaded by

csraghavi6
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
9 views14 pages

Data Structure

The document presents the Bellman-Ford Algorithm, which finds the shortest path from a single source to all vertices in a weighted graph, accommodating negative weight edges. It outlines the algorithm's steps, including initialization, edge relaxation, and negative cycle detection, and provides a practical scenario involving a flight booking system. The conclusion emphasizes the algorithm's effectiveness and flexibility in handling various graph conditions.

Uploaded by

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

DEPARTMENT OF COMPUTER SCIENCE

AND ENGINEERING
DATA STRUCTURES AND ALGORITHMS FOR
PROBLEM SOLVING(MCS103)
TOPIC: BELLMANFORD ALGORITHM

PRESENTED BY: GUIDED BY:


RAGHAVI CS 1KS24SCS05 DR. VIJAYALAXMI MEKALI
ASSOCIATE PROFESSOR,
K S INTITUTE OF
TECHNOLOGY
KANAKAPURA ROAD,
BENGALORE
INDEX(TABLE OF
CONTENTS)
• Introduction
• Algorithm steps
• Scenario and C program code
• Tree model representation
• Conclusion
INTRODUCTI
ON
The Bellman-Ford Algorithm finds the shortest path from a single source to
all other vertices in a weighted graph. Unlike Dijkstra’s algorithm, it can
handle negative weight edges.
Key Features:
Works with both positive and negative weights.
Runs in O(V × E) time complexity, where V is the number of vertices and E is
the number of edges.
Uses relaxation to progressively update the shortest path estimates.
Algorithm
steps
How It Works:
Initialize distances from the source to all vertices as infinity (∞), except for the
source itself, which is set to 0.
Relax all edges (V-1) times, where V is the number of vertices.
Perform an extra iteration to check for negative weight cycles. If further
relaxation is possible, a negative weight cycle exists.
Scenario and C program code

• A flight booking system needs to find the cheapest flight route between NYC to
Miami cities. Each route has a different ticket price (edge weight). Edge
representation and path detection .
Graph representation or tree model
representation
• (NYC) NYC-> New York City
/ \
300 200
/ \
(LA)------(Chicago) LA-> Las Angels
\ / |
150 100 250
\ / |
(Dallas)----(Miami)
C
program
•.
Output
Conclusi
on
• The Bellman-Ford algorithm is a powerful and flexible single-source
shortest path algorithm that works even for graphs with negative weight
edges
THANK YOU

You might also like