Hey there! Let's work through these two graph problems step by step—they're both practical and need a bit of careful thinking to get right. Here's how I'd approach each:

1. Print all shortest paths between two specified nodes in an undirected weighted graph #

First, let's clarify: we need every path where the total edge weight equals the shortest possible distance between the start node s and end node t. Here's a reliable method:

Step 1: Compute shortest distances and track predecessors #

Use an algorithm like Dijkstra's (if all edge weights are non-negative) or Bellman-Ford (if negative weights exist, but watch out for negative cycles—they make shortest paths undefined). The key tweak here is instead of storing a single predecessor for each node, we store a list of predecessors:

• When you find that going through node u gives a path to v with the same length as the current shortest distance to v, add u to v's predecessor list.
• If going through u gives a shorter path to v, update v's shortest distance and reset its predecessor list to just u.

Step 2: Backtrack from the end node to find all paths #

Once you have the predecessor lists, start from the end node t and recursively trace back to the start s. Each time you hit s, reverse the path you've built to get a valid shortest path from s to t.

Here's a quick pseudocode example of the backtracking function:

def find_all_shortest_paths(s, t, prev, current_path, result):
    current_path.append(t)
    if t == s:
        # Reverse to get s -> ... -> t
        result.append(current_path[::-1])
    else:
        for predecessor in prev[t]:
            find_all_shortest_paths(s, predecessor, prev, current_path.copy(), result)
    current_path.pop()

# Initialize result list and call the function
result = []
find_all_shortest_paths(s, t, predecessor_list, [], result)

Notes #

• If your graph has negative cycles, first run a cycle detection check (Bellman-Ford can do this). If a cycle is reachable from s and can reach t, there are infinitely many "shortest" paths, so you'll need to handle that case explicitly.
• For large graphs, consider iterative backtracking instead of recursion to avoid stack overflow.

2. Find all node pairs with the smallest distance in an undirected weighted graph (integer edge weights) #

The goal here is to find every pair of distinct nodes (u, v) where their shortest path distance is the smallest possible across the entire graph. Here's how to do it:

Step 1: Compute all-pairs shortest paths #

Choose an algorithm based on your graph's density:

• Floyd-Warshall: Great for dense graphs (O(n³) time, where n is the number of nodes). It's easy to implement and handles negative weights (as long as there are no negative cycles—if there are, some node pairs will have unbounded shortest paths).
• Dijkstra's for each node: Better for sparse graphs (O(n(m + n log n)) time with a priority queue, where m is the number of edges). Only works if all edge weights are non-negative.

Step 2: Find the minimum distance and collect all matching pairs #

• Initialize a variable min_distance to a very large value (like infinity).
• Iterate over all unordered pairs of distinct nodes (u, v) (since the graph is undirected, (u, v) is the same as (v, u)):
  • If the shortest distance between u and v is less than min_distance, update min_distance and reset your list of pairs to just (u, v).
  • If the distance equals min_distance, add (u, v) to your list (make sure you don't duplicate pairs, e.g., only add (u, v) where u < v if you're using integer node IDs).

Notes #

• Ignore pairs where the shortest distance is infinity (they're disconnected).
• If there's a negative cycle, any node pair that can be part of paths looping the cycle will have an unbounded (negative infinity) shortest distance. In this case, all such pairs are your answer (or you can report that no finite minimum exists).
• If all edge weights are positive, the minimum distance will be the smallest edge weight in the graph—but don't assume this! If there's a path with multiple edges that sums to a smaller value (only possible with negative weights), you have to compute all-pairs paths to catch it.

内容的提问来源于stack exchange，提问作者unglinh279