How to Implement the Probabilistic Shortest Path Algorithm in Python

The Probabilistic Shortest Path Routing Algorithm is a technique used in optical networks to find the most efficient route between two nodes. Unlike greedy algorithms such as Dijkstra's, this approach evaluates all possible paths between a source and destination, calculates a distance ratio (probability) for each path, and selects the one with the minimum ratio. This guarantees an optimal solution.

This algorithm is particularly relevant in optical networking, where efficient data transfer must balance minimal hardware cost (optical cables, WDM components, multiplexers) with minimal latency. In this guide, you will learn how the algorithm works, walk through detailed examples, and see a complete Python implementation.

How the Algorithm Works

The core idea is simple: instead of greedily choosing the next closest node at each step, the algorithm considers every simple path between the source and destination, then picks the best one based on a probability metric.

Steps

Find all simple paths between the source node and the destination node.
Calculate the total distance across all paths: D = d(P1) + d(P2) + ... + d(Pn).
Compute the distance ratio (probability) for each path: probability(Pi) = d(Pi) / D.
Select the path with the minimum distance ratio as the shortest path.

info

The path with the smallest distance ratio will always be the path with the smallest absolute distance, since all ratios share the same denominator D. The probabilistic framing is useful in optical network contexts where link utilization and load balancing factor into routing decisions.

Walkthrough Example

Consider a simple graph with four nodes: A, B, C, and D:

A --3-- B
|       |
4       3
|       |
D --3-- B
|
2
|
C --5-- B

All possible paths from A to B:

Path	Distance	Distance Ratio
P1: A → B	3	3/17 ≈ 0.176
P2: A → C → B	2 + 5 = 7	7/17 ≈ 0.412
P3: A → D → B	4 + 3 = 7	7/17 ≈ 0.412

Total distance: D = 3 + 7 + 7 = 17

The minimum distance ratio is 3/17 for path P1, so the shortest path is A → B.

Python Implementation

The following implementation demonstrates the algorithm on a 7-node network, finding the probabilistic shortest path between any two nodes.

Graph Setup and Helper Functions

# Number of nodes in the network
NODES = 7

# Small value representing no direct link between nodes
INVALID = 0.001

# Initialize adjacency matrix with INVALID (no connection)
distance_links = [[INVALID for _ in range(NODES)] for _ in range(NODES)]

# Define the actual link distances (bidirectional)
edges = [
    (0, 1, 7), (1, 2, 8), (0, 2, 9),
    (0, 3, 9), (3, 4, 4), (4, 5, 6),
    (2, 5, 4), (4, 6, 8), (0, 6, 5),
]

for u, v, w in edges:
    distance_links[u][v] = w
    distance_links[v][u] = w


def get_neighbors(node):
    """Returns a list of nodes directly connected to the given node."""
    return [i for i in range(NODES) if distance_links[node][i] != INVALID]

Finding All Simple Paths

A simple path visits each node at most once. This function uses an iterative depth-first search to yield all simple paths between start and end:

def find_simple_paths(start, end):
    """Yields all simple paths from start to end using iterative DFS."""
    visited = {start}
    node_stack = []
    index_stack = []
    current = start
    i = 0

    while True:
        neighbors = get_neighbors(current)

        # Skip already-visited neighbors
        while i < len(neighbors) and neighbors[i] in visited:
            i += 1

        if i >= len(neighbors):
            # Backtrack
            visited.remove(current)
            if not node_stack:
                break
            current = node_stack.pop()
            i = index_stack.pop()

        elif neighbors[i] == end:
            # Found a complete path
            yield node_stack + [current, end]
            i += 1

        else:
            # Explore deeper
            node_stack.append(current)
            index_stack.append(i + 1)
            visited.add(neighbors[i])
            current = neighbors[i]
            i = 0

Computing the Shortest Path

def find_probabilistic_shortest_path(source, destination):
    """
    Finds the shortest path using the probabilistic distance ratio method.
    """
    # Step 1: Find all simple paths
    all_paths = list(find_simple_paths(source, destination))

    if not all_paths:
        print(f"No path found from node {source} to node {destination}.")
        return

    # Step 2: Calculate the distance of each path
    path_distances = []
    for path in all_paths:
        distance = sum(
            distance_links[path[j - 1]][path[j]] for j in range(1, len(path))
        )
        path_distances.append(distance)

    # Step 3: Calculate total distance across all paths
    total_distance = sum(path_distances)

    # Step 4: Calculate distance ratio (probability) for each path
    distance_ratios = [d / total_distance for d in path_distances]

    # Step 5: Find the path with the minimum distance ratio
    min_index = distance_ratios.index(min(distance_ratios))
    shortest_path = all_paths[min_index]

    # Display results
    print(f"Source: Node {source} | Destination: Node {destination}")
    print(f"{'Path':<30} {'Distance':<12} {'Ratio':<10}")
    print("-" * 52)

    for i, path in enumerate(all_paths):
        path_str = " → ".join(str(n) for n in path)
        marker = " ← shortest" if i == min_index else ""
        print(f"{path_str:<30} {path_distances[i]:<12.1f} {distance_ratios[i]:<10.4f}{marker}")

    print(f"\nShortest path: {shortest_path}")
    print(f"Distance: {path_distances[min_index]}")

    return shortest_path

Running the Algorithm

if __name__ == "__main__":
    find_probabilistic_shortest_path(source=1, destination=5)

Output:

Source: Node 1 | Destination: Node 5
Path                           Distance     Ratio     
----------------------------------------------------
1 → 0 → 2 → 5                  20.0         0.1282    
1 → 0 → 3 → 4 → 5              26.0         0.1667    
1 → 0 → 6 → 4 → 5              26.0         0.1667    
1 → 2 → 0 → 3 → 4 → 5          36.0         0.2308    
1 → 2 → 0 → 6 → 4 → 5          36.0         0.2308    
1 → 2 → 5                      12.0         0.0769     ← shortest

Shortest path: [1, 2, 5]
Distance: 12
...

tip

The exact output will vary depending on the number of simple paths discovered. The key result is that the path with the minimum distance ratio is always the path with the shortest absolute distance.

Understanding Distance Ratio Calculation

To clarify the math behind the algorithm, here is a focused breakdown:

# Example with 3 paths
# P1 distance = 12, P2 distance = 30, P3 distance = 26

total = 12 + 30 + 26  # equals 68

ratio_p1 = 12 / 68    # ≈ 0.176 (minimum, therefore shortest)
ratio_p2 = 30 / 68    # ≈ 0.441
ratio_p3 = 26 / 68    # ≈ 0.382

The path with distance 12 has the smallest ratio, confirming it as the shortest path.

Common Pitfall: Using INVALID as Zero

A frequent mistake is using 0 to represent non-existent links in the adjacency matrix. This causes problems because the get_neighbors function would incorrectly treat every node as a neighbor.

Wrong approach:

# Using 0 for no connection; this is WRONG
distance_links = [[0 for _ in range(NODES)] for _ in range(NODES)]

This would make get_neighbors() return all nodes (including unconnected ones), leading to incorrect paths.

Correct approach:

# Use a small sentinel value or use a different data structure
INVALID = 0.001
distance_links = [[INVALID for _ in range(NODES)] for _ in range(NODES)]

note

An even better approach for production code is to use an adjacency list (dictionary of lists) instead of an adjacency matrix. This avoids the sentinel value problem entirely and uses less memory for sparse graphs:

graph = {
    0: [(1, 7), (2, 9), (3, 9), (6, 5)],
    1: [(0, 7), (2, 8)],
    2: [(1, 8), (0, 9), (5, 4)],
    # ...
}

Advantages Over Greedy Shortest Path Algorithms

Aspect	Greedy Algorithms (e.g., Dijkstra)	Probabilistic Shortest Path
Approach	Makes locally optimal choices at each step	Evaluates all possible paths globally
Optimality guarantee	Optimal for non-negative weights (Dijkstra)	Always optimal as it examines all paths
Time complexity	O(V² ) or O(E log V) with a min-heap	O(V!) in worst case where all simple paths are checked
Best for	Large general-purpose graphs	Small-to-medium optical networks
Priority updates	Required	Not needed

caution

Because this algorithm enumerates all simple paths, its time complexity can be exponential in the worst case. It is best suited for small-to-medium networks common in optical routing scenarios. For very large graphs, Dijkstra's algorithm or A* search would be more practical.

Summary

The Probabilistic Shortest Path Routing Algorithm provides a globally optimal solution by evaluating every possible path between two nodes and selecting the one with the minimum distance ratio. While it is computationally more expensive than greedy alternatives, it guarantees accuracy. This makes it particularly valuable in optical network design where correctness is critical.

Key takeaways:

The algorithm finds all simple paths between source and destination.
It calculates a distance ratio for each path relative to the total distance of all paths.
The path with the minimum ratio is the shortest path.
It is best suited for small-to-medium networks due to its exponential worst-case complexity.
For large-scale graphs, consider Dijkstra's algorithm or A* search instead.

How the Algorithm Works​

Steps​

Walkthrough Example​

Python Implementation​

Graph Setup and Helper Functions​

Finding All Simple Paths​

Computing the Shortest Path​

Running the Algorithm​

Understanding Distance Ratio Calculation​

Common Pitfall: Using INVALID as Zero​

Advantages Over Greedy Shortest Path Algorithms​

Summary​

Table of Contents