Shortest Path Problem

Definitions

A path is a sequence of nodes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.

Single Source Shortest Path (SSSP)

Given a graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G(V,E), w(e) } , source node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S } , 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: Bellman Ford

All shortest path must have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leq n - 1 } 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) for all (u, a) in E)

Time complexity: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(V^2) }

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))