C# 實現路徑規劃 (最短路徑) 算法 (4) — RoutePlanner 核心遞迴實現

Dijkstra 演算法核心步驟

1. 建立 PlanCourse 記錄源點到各節點最小權值，初始化：直達邊賦權值，其餘設 double.MaxValue。
2. 選取未處理且累積權值最小的節點 TargetNode，以其邊鬆弛更新鄰居權值與路徑，標記 TargetNode 為已處理。
3. 重複步驟 2，直到所有可達節點皆處理完畢。
4. 從 PlanCourse 取出目標節點的 PassedPath 作為結果。

RoutePlanner 完整實現

public class RoutePlanner
{
    public RoutePlanResult Plan(ArrayList nodeList, string originID, string destID)
    {
        var planCourse = new PlanCourse(nodeList, originID);
        Node curNode = GetMinWeightRudeNode(planCourse, nodeList, originID);

        while (curNode != null)
        {
            var curPath = planCourse[curNode.ID];
            foreach (Edge edge in curNode.EdgeList)
            {
                var targetPath = planCourse[edge.EndNodeID];
                double tempWeight = curPath.Weight + edge.Weight;
                if (tempWeight < targetPath.Weight)
                {
                    targetPath.Weight = tempWeight;
                    targetPath.PassedIDList.Clear();
                    for (int i = 0; i < curPath.PassedIDList.Count; i++)
                        targetPath.PassedIDList.Add(curPath.PassedIDList[i].ToString());
                    targetPath.PassedIDList.Add(curNode.ID);
                }
            }
            planCourse[curNode.ID].BeProcessed = true;
            curNode = GetMinWeightRudeNode(planCourse, nodeList, originID);
        }

        return GetResult(planCourse, destID);
    }

    private RoutePlanResult GetResult(PlanCourse planCourse, string destID)
    {
        var pPath = planCourse[destID];
        if (pPath.Weight == int.MaxValue)
            return new RoutePlanResult(null, int.MaxValue);

        string[] passedNodeIDs = new string[pPath.PassedIDList.Count];
        for (int i = 0; i < passedNodeIDs.Length; i++)
            passedNodeIDs[i] = pPath.PassedIDList[i].ToString();

        return new RoutePlanResult(passedNodeIDs, pPath.Weight);
    }

    private Node GetMinWeightRudeNode(PlanCourse planCourse, ArrayList nodeList, string originID)
    {
        double weight = double.MaxValue;
        Node destNode = null;
        foreach (Node node in nodeList)
        {
            if (node.ID == originID) continue;
            var pPath = planCourse[node.ID];
            if (pPath.BeProcessed) continue;
            if (pPath.Weight < weight)
            {
                weight = pPath.Weight;
                destNode = node;
            }
        }
        return destNode;
    }
}

關鍵類別

• RoutePlanResult：封裝路徑節點 ID 陣列與總權值。
• PassedPath：Weight (累積權值)、PassedIDList (路徑節點 ID)、BeProcessed (是否已展開)。

此實現為經典 Dijkstra 演算法 (O(V²) 版本)，適合教學與中小型圖。大型圖建議使用優先佇列優化至 O(E log V)。