请求修改Dijkstra算法以实现最宽路径计算（附代码片段）

老哥，我懂你现在的困扰——核心逻辑你已经摸准了（把求和换成取最小、取最小换成取最大），但落实到代码上就卡壳了对吧？我结合你给出的代码片段，给你拆解下关键的修改点：

先明确最宽路径的核心 #

最宽路径（也叫最大瓶颈路径）的目标是：找到从起点到每个节点的路径中，路径里最小边的权重尽可能大。和Dijkstra的“累加权重找最小总和”逻辑正好相反，我们要做的是追踪路径的“瓶颈”（路径中最小的边），并保留最大的那个瓶颈值。

具体代码修改点 #

你的代码里已经有了settledNodes、unSettledNodes、前驱节点映射这些基础结构，只需要针对以下几个关键部分修改：

1. 替换距离存储的初始化 #

原来的Dijkstra里，你应该有一个类似Map<Vertex, Integer> distance的结构，用来存储起点到各节点的最短距离。现在我们要改成存储最大瓶颈宽度，建议重命名为maxWidth：

// 初始化：起点的宽度设为最大值（自身到自身无瓶颈），其他节点初始为0（未连通）
Map<Vertex, Integer> maxWidth = new HashMap<>();
for (Vertex node : nodes) {
    maxWidth.put(node, 0);
}
maxWidth.put(startNode, Integer.MAX_VALUE);

2. 修改松弛操作的判断逻辑 #

原来的松弛操作是判断“通过当前节点到目标节点的总距离是否更短”，现在要改成判断“通过当前节点到目标节点的路径瓶颈是否更大”：
假设你原来的松弛代码大概是这样（基于你给出的片段）：

// 原Dijkstra的松弛逻辑
int newDistance = distance.get(currentNode) + edge.getWeight();
if (newDistance < distance.get(neighbor)) {
    distance.put(neighbor, newDistance);
    predecessors.put(neighbor, currentNode);
    unSettledNodes.add(neighbor);
}

现在修改为：

// 最宽路径的松弛逻辑
int newBottleneck = Math.min(maxWidth.get(currentNode), edge.getWeight());
if (newBottleneck > maxWidth.get(neighbor)) {
    maxWidth.put(neighbor, newBottleneck);
    predecessors.put(neighbor, currentNode);
    unSettledNodes.add(neighbor);
}

这里的核心是：通过currentNode到neighbor的路径瓶颈，是currentNode已有的最大瓶颈和当前边权重的较小值（因为路径的瓶颈由最窄的边决定），如果这个新瓶颈比neighbor当前的瓶颈更大，就更新。

3. 修改未处理节点的选择逻辑 #

原来的Dijkstra会从unSettledNodes中选择距离最小的节点，现在要改成选择瓶颈最大的节点。比如你原来可能有一个getLowestDistanceNode方法，现在要替换成getMaxBottleneckNode：

private Vertex getMaxBottleneckNode(Set<Vertex> unSettledNodes, Map<Vertex, Integer> maxWidth) {
    Vertex maxNode = null;
    int maxValue = -1;
    for (Vertex node : unSettledNodes) {
        int currentWidth = maxWidth.get(node);
        if (currentWidth > maxValue) {
            maxValue = currentWidth;
            maxNode = node;
        }
    }
    return maxNode;
}

在主循环里，把原来调用getLowestDistanceNode的地方换成这个方法就行。

4. 变量命名的小调整 #

为了避免混淆，建议把所有和“距离”相关的变量名（比如distance、lowestDistance）改成和“宽度/瓶颈”相关的，比如maxWidth、highestBottleneck，这样代码可读性会高很多。

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