Revision as of 01:32, 28 February 2024

Definitions

A path is a sequence of nodes $x_{1},x_{2},x_{3},\ldots ,x_{i}$ such that for all consecutive nodes, there exist an edge

Let there be a weight assigned to each edge.

Given a graph $G(V,E),w(e)$ , source node $S$ , outupt the shortest path from the source

   * Single destination problem: shortest path from all nodes to a
     single destination
   * Single pair problem: Shortest path between input pair

@@ Line 1: / Line 1: @@
-= Problem Description =
+= Definitions =
-A path is a sequence of nodes
+A path is a sequence of nodes <math> x_1, x_2, x_3, \ldots, x_i </math>
+such that for all consecutive nodes, there exist an edge
-<math>
+Let there be a weight assigned to each edge.
-x_1, x_2, x_3, \ldots, x_i
-</math>
-such that for all consecutive nodes, there exist an edge
+= Single Source Shortest Path (SSSP) =
+Given a graph <math>G(V,E), w(e)</math>, source node <math>S</math>,
+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