Shortest Path Problem: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
Line 13: | Line 13: | ||
== Variants == | == Variants == | ||
* Single destination problem: shortest path from all nodes to a | |||
single destination | |||
* Single pair problem: Shortest path between input pair |
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