Shortest Path Problem: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
Line 8: | Line 8: | ||
= Single Source Shortest Path (SSSP) = | = Single Source Shortest Path (SSSP) = | ||
Given a graph <math>G(V,E), w(e)</math>, source node <math>S</math>, | Given a graph <math> G(V,E), w(e) </math>, source node <math> S </math>, | ||
outupt the shortest path from the source | outupt the shortest path from the source | ||
Revision as of 01:33, 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