Shortest Path Problem: Difference between revisions

From Rice Wiki
No edit summary
No edit summary
Line 15: Line 15:
* Single destination problem: shortest path from all nodes to a single destination
* Single destination problem: shortest path from all nodes to a single destination
* Single pair problem: Shortest path between input pair
* Single pair problem: Shortest path between input pair
== Implementation ==
All shortest path must have <math> \leq n - 1 </math> edges. If this
condition is not satisfied, there is a cycle in in the path, and
therefore it is not the shortest.

Revision as of 01:37, 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.