Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

Comparison

Compared to the Dijkstra Algorithm:

  • Bellman-Ford can handle negative weights whereas Dijkstra can only handle positives.
  • Dijsktra's algorithm Time Complexity: O(V^2)
  • Bellman Ford Time Complexity: O(V^3)

Dijkstra Running Cases:

  • Worst Case O(|E|+|V|log|V|)

Bellman Ford Running Cases:

Best Case O(|E|)

Worst Case O(|V||E|)

Algorithm Psuedocode

Bellman-Ford Psuedocode

Relaxation Psuedocode

Explanation

Application

Routing information protocol

CPU Gate

Background

Richard E. Bellman

  • The people:
  • First proposed by Alfonso Shimbel in 1955
  • Published by Lester Ford in 1956 and by Richard Bellman in 1958
  • Also by Edward F. Moore in 1957
  • What does it do?
  • Bellman-Ford is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph
  • Why?
  • created to find the shortest path when there is a negative cycle in a graph

Lester Ford Jr.

Bellman-Ford Algorithm

By: Eunice Arokiadoss and Fehmina Hasan

Learn more about creating dynamic, engaging presentations with Prezi