如何改进Dijkstra算法实现SDN最短路径路由及代码优化

我正在使用Floodlight控制器，基于Dijkstra算法模拟SDN最短路径路由，目的是优化两台主机间的路由，想请教以下代码的可优化之处：

public static Graph calculateShortestPathFromSource(Graph graph, Node source) 
{
    source.setDistance(0);
    Set<Node> settledNodes = new HashSet<>();
    Set<Node> unsettledNodes = new HashSet<>();
    unsettledNodes.add(source);
    while (unsettledNodes.size() != 0) {
        Node currentNode = getLowestDistanceNode(unsettledNodes);
        unsettledNodes.remove(currentNode);
        for (Map.Entry < Node, Integer> adjacencyPair:
          currentNode.getAdjacentNodes().entrySet()) {
            Node adjacentNode = adjacencyPair.getKey();
            Integer edgeWeight = adjacencyPair.getValue();
            if (!settledNodes.contains(adjacentNode)) {
                CalculateMinimumDistance(adjacentNode, edgeWeight, currentNode);
                unsettledNodes.add(adjacentNode);
            }
        }
        settledNodes.add(currentNode);
    }
    return graph;
}

/**
 * 获取距离最小的节点
 */ 
private static Node getLowestDistanceNode(Set < Node > unsettledNodes) 
{
    Node lowestDistanceNode = null;
    int lowestDistance = Integer.MAX_VALUE;
    for (Node node: unsettledNodes) {
        int nodeDistance = node.getDistance();
        if (nodeDistance < lowestDistance) {
            lowestDistance = nodeDistance;
            lowestDistanceNode = node;
        }
    }
    return lowestDistanceNode;
}

/** 
 * 更新节点的最短距离与路径
 */
private static void CalculateMinimumDistance(Node evaluationNode, Integer edgeWeigh, Node sourceNode) 
{
    Integer sourceDistance = sourceNode.getDistance();
    if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) 
    {
        evaluationNode.setDistance(sourceDistance + edgeWeigh);
        LinkedList<Node> shortestPath = new LinkedList<>(sourceNode.getShortestPath());
        shortestPath.add(sourceNode);
        evaluationNode.setShortestPath(shortestPath);
    }
}

可优化之处： #

• 用优先队列替代线性查找，提升核心性能
  当前getLowestDistanceNode方法需要遍历整个未处理节点集合找距离最小的节点，时间复杂度为O(n)。在SDN拓扑节点较多的场景下，改用PriorityQueue（优先队列）可将取最小节点的操作复杂度降至O(logn)，大幅提升算法效率。处理节点距离更新时，可允许重复入队，后续处理节点时先判断是否已被结算，若已结算则直接跳过。

• 避免未处理节点重复入队
  当前代码每次更新邻接节点后都会无条件将其加入unsettledNodes，导致集合中出现重复节点，增加后续遍历开销。可以在加入前判断节点是否已在集合中；如果使用优先队列，可允许重复入队但在处理时过滤已结算的节点。

• 优化路径存储方式，降低内存与GC开销
  当前CalculateMinimumDistance方法每次更新路径都会新建LinkedList并复制源节点的完整路径，在大型拓扑中频繁创建列表会加重GC负担。建议改为每个节点仅存储前驱节点，当需要完整路径时，从目标节点回溯到源节点再生成路径，这样内存占用更少，操作更高效。

• 修正命名与注释规范

  • 方法名遵循Java小驼峰规则：将CalculateMinimumDistance改为calculateMinimumDistance
  • 参数拼写错误：edgeWeigh修正为edgeWeight
  • 注释描述修正：比如getLowestDistanceNode的注释应明确是“获取未处理节点中距离最小的节点”，而非模糊的“获取最小距离”

• 适配Floodlight多线程环境，保证线程安全
  Floodlight是多线程控制器，当前代码直接修改Node的distance和shortestPath属性，存在线程安全风险。可以采用两种方式优化：一是使用线程安全的数据结构存储节点状态；二是每次路由计算时创建节点的副本，避免修改原拓扑节点的状态，这样同一个拓扑可同时处理多个路由请求。

• 增加提前终止逻辑，适配SDN场景需求
  在SDN中我们通常只需要计算源主机到目标主机的最短路径，而非所有节点。可以修改方法，传入目标节点参数，当当前处理的节点就是目标节点时，直接跳出循环提前终止计算，节省不必要的资源消耗。

• 补充边界与异常处理

  • 增加source为null的判断，避免空指针异常
  • 校验edgeWeight的合法性：SDN中链路权重通常为正数，若出现null或负数应抛出异常或进行默认处理

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