Hi @rossbar and NetworkX team,

Thank you for your response!

There is indeed a key difference between using nx.dijkstra_path(G, src, dst, weight="inv") and directly computing the maximum bottleneck path. While Dijkstra’s algorithm optimizes for the sum of edge weights (shortest path), the maximum bottleneck path problem optimizes for the maximum of the minimum edge weight along the path. This distinction is fundamental because:

1. Dijkstra’s algorithm with inverse weights does not necessarily yield the optimal bottleneck path

   • Since Dijkstra minimizes the total weight, paths with larger individual bottleneck values may not be preferred.
   • Example: If we have two paths from s to t, one with edge weights [100, 100, 1] and another with [50, 50, 50], Dijkstra’s algorithm (with inverse weights) would likely prefer the first path, even though its bottleneck is only 1, whereas the second path has a bottleneck of 50.

2. Recomputing the bottleneck value after obtaining the path is not sufficient

   • As you pointed out, Dijkstra's algorithm returns a sequence of nodes, so we can reconstruct the weight along the path afterward.
   • However, this approach does not guarantee that the path actually maximizes the minimum edge weight.
   • Example: Consider a graph where the shortest path (in terms of sum of weights) has a bottleneck of 5, but an alternative path with a slightly longer total weight sum has a bottleneck of 20. The naive approach would select the wrong path.
   • Thus, the path must be constructed while considering the bottleneck value at each step, rather than selecting a path based on total weight and then computing its bottleneck afterward.

3. Modified Dijkstra-like algorithm that prioritizes paths by their bottleneck value

   • Instead of summing edge weights, we maintain a priority queue where the highest bottleneck path is always expanded first.
   • This ensures that the algorithm efficiently finds the path with the highest possible bottleneck.

Example Implementation

To illustrate this, I have implemented the maximum bottleneck path algorithm as a modification of Dijkstra’s approach. The implementation is available in my repository:
🔗 GitHub Repository: Modified Dijkstra for Max Bottleneck Paths

def max_load_path(G, source, target, weight="weight"):
    """
    Finds a path from source to target that maximizes the minimum edge weight along the path (bottleneck capacity).
    Uses a Dijkstra-like algorithm but propagates the minimum encountered edge weight instead of summing weights.
    """
    from heapq import heappop, heappush
    import networkx as nx

    # Initialize bottleneck values, predecessors, and priority queue
    bottleneck = {node: float("-inf") for node in G}
    bottleneck[source] = float("inf")
    pq = [(-bottleneck[source], source)]
    pred = {node: None for node in G}

    while pq:
        curr_bottle_neg, u = heappop(pq)
        curr_bottle = -curr_bottle_neg  # Convert back to positive

        if u == target:
            break  # Early exit when reaching the target

        for v in G.neighbors(u):
            edge_weight = G[u][v].get(weight, 1)
            new_bottleneck = min(curr_bottle, edge_weight)

            if new_bottleneck > bottleneck[v]:
                bottleneck[v] = new_bottleneck
                pred[v] = u
                heappush(pq, (-new_bottleneck, v))

    # Path reconstruction
    if bottleneck[target] == float("-inf"):
        raise nx.NetworkXNoPath(f"No path found from {source} to {target}")

    path = []
    current = target
    while current is not None:
        path.append(current)
        current = pred[current]
    path.reverse()

    return path

Reasons for requesting it as a standard module for Network X

• Minimal change from standard Dijkstra’s implementation
  • The algorithm structure is nearly identical, but the priority queue logic is adapted to maximize the minimum edge weight.
• Useful in networking, logistics, and routing
  • This algorithm is commonly used in network traffic engineering, emergency response routing, and maximum throughput problems.
• While it is possible to modify existing functions, having it as a built-in function in NetworkX would be more convenient
  • Of course, users can modify the existing Dijkstra implementation to achieve this, but having a standard module that directly computes the maximum bottleneck path would be valuable for applications in network capacity planning, congestion-aware routing, and bandwidth-sensitive applications.

Would the NetworkX team be interested in integrating this as a standard feature?
I’d be happy to contribute a pull request for further discussion.

Thank you for your consideration! 🚀

Best,
Takumi Senaha

Yes, this seems like a good addition to NetworkX.
Can you prepare a PR for it?
Thanks!

Hi @dschult
Thank you for your response!

Since this algorithm focuses on maximizing the bottleneck capacity rather than minimizing path weight, I believe it would be better to create a new module rather than adding it to shortest_paths/.

I plan to introduce a new module named maximum_load_paths/ under networkx/algorithms/ to keep it distinct while maintaining consistency with other algorithm categories.

Can you prepare a PR for it?

I will proceed by forking the repository and preparing a PR.

Best regards

Great -- but make the new module maximum_load_paths.py (a single file) rather than a new directory the way shortest_paths is set up. You could use cycles.py or d_separation.py as models of how that would work. The docs will need a matching rst file as well. Let us know if you have questions. And submitting a partial PR gives a good way to ask the questions and get feedback if that works for you.