Shortest Path Problem

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.

Single Source Shortest Path (SSSP)

Given a graph $G(V,E),w(e)$, source node $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 $\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: $O(V^{2}+VE)$

• Sparse: $O(V^{2})$
• Dense: $O(V^{3})$

// G: Graph with vertices (V) and edges (E)
// w[e]: weight of edge e
// S: starting node
Bellman-Ford(G, w, S)
    V, E = G
    pi[v] = null for all v  // traceback
    
    // initialize all shortest path algo
    d[v] = infty for all v
    d[s] = 0
    for i from 1 to |V| - 1:
        for all (u,v) in E
            if d[v] > d[u] + w(u, v):
                d[v] = d[u] + w(u,v)
                pi[v] = u;
    
    for all (u, v) in E:
        if d[v] > d[u] + w(u, v):
            // has negative cycle
            return false

This accounts for negative edges but not negative cycles. Bellman Ford can detect it by running an extra time, since if there is a negative cycle, the run time will improve.