Shortest Path Problem: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
Line 31: | Line 31: | ||
=== Bellman Ford Algorithm === | === Bellman Ford Algorithm === | ||
Time complexity: <math> O(V^2) </math> | |||
<pre> | <pre> | ||
for e = 1 to n - 1: | for e = 1 to n - 1: |
Revision as of 01:48, 28 February 2024
Definitions
A path is a sequence of nodes such that for all consecutive nodes, there exist an edge
Let there be a weight assigned to each edge.
Single Source Shortest Path (SSSP)
Given a graph , source node , outupt the shortest path from the source
Variants
- Single destination problem: shortest path from all nodes to a single destination
- Single pair problem: Shortest path between input pair
Implementation
All shortest path must have edges. If this condition is not satisfied, there is a cycle in in the path, and therefore it is not the shortest.
OPT(a, n-1) = min(w(u,a) + OPT(n-1, u))
where
Bellman Ford Algorithm
Time complexity:
for e = 1 to n - 1: for each u in V: OPT(u, e) = min(w(v,u) + OPT(v, e-1) for all (v, u)) OPT(u, e) = min(OPT(u,e), OPT(u, e-1))