Identifying Edges on Shortest Paths in Directed Graphs

To determine which edges can lie on a shortest path from source S to target T in a directed graph, compute shortest distances from S to all nodes. Then, perform a reverse BFS starting from T on the transposed graph. For each dequeued node cur and its neighbor nex in the transposed graph, if Dist[nex] == Dist[cur] - weight(cur->nex) holds, the original edge nex->cur may belong to a shortest S-T path.

Example Problem: LeetCode Weekly Contest 394: Find Edges in Shortest Paths.

Multi-Source Shortest Paths

Given multiple sources s0, s1, ..., sN, find for each node x the shortest distance to any source.

  • Naive Approach: Run a single-source shortest path algorithm from every node, taking O(V * cost_per_SSSP) time.
  • Optimized for Undirected Graphs: If edge weights are symmetric (undirected graph), run a single multi-source shortest path from all sources simultaneously. The resulting dist[x] directly gives the answer.

Illustrative Problem: Multi-source BFS with unit weights.

Path Extremum Problems

In a directed or undirected graph with a defined path weight function, find the minimum or maximum weight among all S-T paths. Path weight can be any function of edge or node weights (e.g., sum, max, min), but the objective is strictly either minimization or maximization across paths.

Example: Path weight defined as the maximum node weight along the path, seeking the minimum such value.

Analysis of Extremal Paths

Consider graphs with both positive and negative edges, requiring algorithms like SPFA for longest paths (or shortest with negatives). Solvability depends on reachable positive cycles from the start set; if any start node reaches a positive cycle, the problem is unsolvable for those nodes.

Initialization with Uniform Start Values

When all start nodes have the same initial distance (e.g., Dist[S] = 0), after SPFA, Dist[x] represents the total edge weight along an optimal path from some start. Nodes with Dist[x] = initial_value are real start points; others have paths with at least one edge. If all starts are initialized to a constant d, final distances are shifted by d.

Initialization with Distinct Start Values

If start nodes have different initial distences, the algorithm adapts similarly, but paths may originate from different real starts.

Unsolvable Cases and Initialization

If a positive cycle is reachable from any start node, the problem is unsolvable regardless of initial distance settings.

Zero-Weight Edges

For longest paths, a zero-weight edge a->b ensures Dist[b] ≥ Dist[a]. In a zero-weight chain, distances form a non-decreasing sequence. If a node in such a chain has a distance greater than its initial value, a positive cycle exists, making the problem unsolvable.

Shortest Path Fundamentals

Given a weighted graph G, start set S, and distance array Dist[]:

  • G is valid if every Dist[] is either unreachable or uniquely defined.
  • A path is a sequence starting from some s ∈ S.
  • Path distance is the sum of edge weights plus the start's initial distance.
  • Updates use a binary operation (e.g., addition) and comparison (less-than for minimization).
  • The best distance for a node is the minimum over all paths.
  • Best paths may not be unique.

General Algorithm (SPFA-like):

set Dist[all] = INF;
for s in S: Dist[s] = I[s];
while true:
    updated = false;
    for each edge a->b with weight w:
        if Dist[a] + w < Dist[b]:
            Dist[b] = Dist[a] + w;
            updated = true;
    if not updated: break;

Properties:

  • Valid graphs have loop-free best paths (zero-weight loops can be removed).
  • The first node of any best path is a start point.
  • Non-start nodes have path lengths > 0; real start nodes have length 0.
  • Best paths exhibit optimal substructure: any prefix is also a best path.

BFS for 0-1 Weighted Graphs

For graphs with edge weights 0 or 1, use a deque-based BFS (0-1 BFS) to find shortest paths efficiently.

dist[start] = 0;
deque<int> dq;
dq.push_back(start);
while !dq.empty():
    cur = dq.front(); dq.pop_front();
    if visited[cur]: continue;
    visited[cur] = true;
    for each edge cur->nex with weight w:
        int newDist = dist[cur] + w;
        if newDist < dist[nex]:
            dist[nex] = newDist;
            if w == 0: dq.push_front(nex);
            else: dq.push_back(nex);

Proof Sketch: Nodes are processed in non-decreasing distance order due to deque operations. A node may be enqueued multiple times, but the first dequeued instance per distance level yields correct distances.

Directed Acyclic Graphs (DAGs)

In DAGs, all paths are finite, allowing shortest/longest path computation via dynamic programming in topological order.

topo_order = topological_sort(G);
set Dist[all] = INF;
Dist[source] = 0;
for cur in topo_order:
    if Dist[cur] == INF: continue;
    for each edge cur->nex with weight w:
        Dist[nex] = min(Dist[nex], Dist[cur] + w);

Dijkstra's Algorithm

For graphs with non-negative edge weights, Dijkstra's algorithm computes shortest paths using a priority queue.

Positive-Weight Graphs (weights > 0):

  • All best paths have strictly increasing distances.
  • Predecessor sets are acyclic.

Standard Dijkstra (weights ≥ 0):

  • Zero-weight edges may cause multiple best paths; predecessor relations may be cyclic.
  • Dijkstra remains correct, but path reconstruction requires care.

Algorithm:

set Dist[all] = INF;
priority_queue<pair<dist, node>> pq;
for s in S:
    Dist[s] = I[s];
    pq.push({Dist[s], s});
while !pq.empty():
    auto [d, cur] = pq.top(); pq.pop();
    if d != Dist[cur]: continue; // lazy deletion
    for each edge cur->nex with weight w:
        if Dist[cur] + w < Dist[nex]:
            Dist[nex] = Dist[cur] + w;
            pq.push({Dist[nex], nex});

Second-Best Shortest Paths

Find the second-shortest path distance, differing from the best path in edges, with distance either strictly greater (type 1) or possibly equal (type 2).

set Dist[all] = INF, Dist2[all] = INF;
// First phase: update from best paths
for s in S:
    Dist[s] = I[s];
    pq.push({Dist[s], s});
while !pq.empty():
    auto [d, cur] = pq.top(); pq.pop();
    if d != Dist[cur]: continue;
    for each edge cur->nex with weight w:
        int newDist = Dist[cur] + w;
        if newDist < Dist[nex]:
            Dist2[nex] = Dist[nex]; // previous best becomes second-best
            Dist[nex] = newDist;
            pq.push({Dist[nex], nex});
        else if newDist < Dist2[nex]: // for type 2, add: && newDist != Dist[nex]
            Dist2[nex] = newDist;
            pq.push({Dist2[nex], nex});
// Second phase: propagate second-best distances
for node in all:
    if Dist2[node] != INF: pq.push({Dist2[node], node});
while !pq.empty():
    auto [d, cur] = pq.top(); pq.pop();
    if d != Dist2[cur]: continue;
    for each edge cur->nex with weight w:
        if Dist2[cur] + w < Dist2[nex]:
            Dist2[nex] = Dist2[cur] + w;
            pq.push({Dist2[nex], nex});

Counting Shortest Paths

For graphs with strictly positive weights, count the number of distinct shortest paths.

set Dist[all] = INF, Count[all] = 0;
for s in S:
    Dist[s] = I[s];
    Count[s] = 1;
    pq.push({Dist[s], s});
while !pq.empty():
    auto [d, cur] = pq.top(); pq.pop();
    if d != Dist[cur]: continue;
    for each edge cur->nex with weight w:
        if Dist[cur] + w < Dist[nex]:
            Dist[nex] = Dist[cur] + w;
            Count[nex] = Count[cur];
            pq.push({Dist[nex], nex});
        else if Dist[cur] + w == Dist[nex]:
            Count[nex] += Count[cur];

Generalized Dijkstra

Dijkstra extends to any weight operation and order satisfying a triangle-like inequality: if |AB| ≤ |AC|, then |AB| ≤ |AC| + |CB|. Examples include minimization with non-negative sums, maximization with non-positive sums, or maximization with product weights in [0,1].

Floyd-Warshall Algorithm

Compute all-pairs shortest paths in graphs without negative cycles.

for i in range(n):
    for j in range(n):
        dist[i][j] = edge[i][j];
for i in range(n): dist[i][i] = 0;
for mid in range(n):
    for l in range(n):
        for r in range(n):
            dist[l][r] = min(dist[l][r], dist[l][mid] + dist[mid][r]);

Concept: Paths are categorized by their highest intermediate node; each iteration incorporates paths with that node as maximum.

Transitive Closure (Floyd-Boolean)

Compute reachability for any relation with transitivity.

bool reach[n][n] = /* initial relations */;
for mid in range(n):
    for l in range(n):
        if !reach[l][mid]: continue;
        for r in range(n):
            reach[l][r] |= reach[mid][r];

Dynamic Update: Adding a relation (x,y) updates reachability efficiently.

void add_relation(int x, int y):
    if reach[x][y]: return;
    reach[x][y] = true;
    for l in range(n):
        reach[l][y] |= reach[l][x];
    for r in range(n):
        reach[x][r] |= reach[y][r];
    for l in range(n):
        for r in range(n):
            reach[l][r] |= reach[l][x] && reach[y][r];

Minimum Cycle in Undirected Graphs

Find the smallest cycle (≥3 distinct nodes) in an undirected graph by converting to directed edges and using a modified Floyd approach.

int dist[n][n], edge[n][n];
// Initialize with edge weights, dist = edge, dist[i][i] = 0
int bestCycle = INF;
vector<int> cycleNodes;
for mid in range(n):
    for l in range(n):
        for r in range(n):
            if l != r && l != mid && r != mid &&
               edge[l][mid] != INF && edge[mid][r] != INF && dist[l][r] != INF:
                int cycleLen = edge[l][mid] + edge[mid][r] + dist[l][r];
                if cycleLen < bestCycle:
                    bestCycle = cycleLen;
                    cycleNodes = {r, mid, l};
                    // Reconstruct path from l to r using predecessor matrix
    // Floyd update step
    for l in range(n):
        for r in range(n):
            if dist[l][mid] + dist[mid][r] < dist[l][r]:
                dist[l][r] = dist[l][mid] + dist[mid][r];
                pred[l][r] = mid; // store for reconstruction

Fixed-Length Shortest Paths (Pseudo-Floyd)

Find shortest paths with exactly k edges, even with negative cycles, using matrix exponentiation.

void multiply(const int A[n][n], const int B[n][n], int C[n][n]):
    int temp[n][n] = {INF};
    for l in range(n):
        for r in range(n):
            for mid in range(n):
                if A[l][mid] != INF && B[mid][r] != INF:
                    temp[l][r] = min(temp[l][r], A[l][mid] + B[mid][r]);
    copy(C, temp);

int base[n][n]; // base[i][j] = weight of edge i->j, INF if none
int result[n][n]; // result[i][i] = 0, else INF initially
int k = desired_length;
while k > 0:
    if k & 1: multiply(result, base, result);
    multiply(base, base, base);
    k >>= 1;
// result holds shortest distances with exactly k edges

Tags: graph-theory shortest-path algorithms directed-graphs Optimization

Posted on Sat, 16 May 2026 15:21:00 +0000 by dustinnoe

Hot Tags

©2026 Freaks City