您现在的位置：程式碼之家 >> 編程語言 > >> .NET 網頁程式設計 >> C# >> 關於C#

C# 實作 Dijkstra 最短路徑演算法：圖論基礎與完整程式碼

編輯：關於C#

問題定義

給定有向圖 G = (V, E)，每條邊具權重 w(e) ≥ 0。尋找從起點 s 到終點 t 的最小總權重路徑。

核心資料結構

public class Edge
{
    public string From { get; set; }
    public string To { get; set; }
    public double Weight { get; set; }
}

public class Node
{
    public string Id { get; }
    public List OutEdges { get; } = new List();
    public Node(string id) => Id = id;
}

public class PathInfo
{
    public string NodeId { get; }
    public double TotalWeight { get; set; } = double.MaxValue;
    public List Path { get; } = new List();
    public bool Processed { get; set; }
    public PathInfo(string id) => NodeId = id;
}

Dijkstra 演算法實作


public class DijkstraPlanner
{
    public (double TotalWeight, List Path) FindShortestPath(
        IEnumerable nodes, string startId, string targetId)
    {
        var pathTable = nodes.ToDictionary(n => n.Id, n => new PathInfo(n.Id));
        
        // 起點初始化
        pathTable[startId].TotalWeight = 0;
        pathTable[startId].Path.Add(startId);

        // 優先佇列：(目前權重, 節點ID)
        var pq = new PriorityQueue();
        pq.Enqueue(startId, 0);

        while (pq.Count > 0)
        {
            string curId = pq.Dequeue();
            var curInfo = pathTable[curId];
            if (curInfo.Processed) continue;
            curInfo.Processed = true;

            if (curId == targetId) break; // 找到終點可提前結束

            var curNode = nodes.First(n => n.Id == curId);
            foreach (var edge in curNode.OutEdges)
            {
                var nextInfo = pathTable[edge.To];
                double newWeight = curInfo.TotalWeight + edge.Weight;
                if (newWeight < nextInfo.TotalWeight)
                {
                    nextInfo.TotalWeight = newWeight;
                    nextInfo.Path = new List(curInfo.Path) { edge.To };
                    pq.Enqueue(edge.To, newWeight);
                }
            }
        }

        var targetInfo = pathTable[targetId];
        return targetInfo.TotalWeight == double.MaxValue 
            ? (double.MaxValue, null) 
            : (targetInfo.TotalWeight, targetInfo.Path);
    }
}

優先佇列實作 (.NET 6+ 內建)


// .NET 6+ 可直接使用 System.Collections.Generic.PriorityQueue
// .NET Framework / Standard 2.0 需自行實作或引用 NuGet: C5, PriorityQueue

測試範例


var nodes = new List
{
    new Node("A") { OutEdges = { new Edge{From="A",To="B",Weight=10}, new Edge{From="A",To="C",Weight=20}, new Edge{From="A",To="E",Weight=30} } },
    new Node("B") { OutEdges = { new Edge{From="B",To="C",Weight=5}, new Edge{From="B",To="E",Weight=10} } },
    new Node("C") { OutEdges = { new Edge{From="C",To="D",Weight=30} } },
    new Node("D") { OutEdges = { } },
    new Node("E") { OutEdges = { new Edge{From="E",To="D",Weight=20} } },
};

var planner = new DijkstraPlanner();
var (weight, path) = planner.FindShortestPath(nodes, "A", "D");
Console.WriteLine($"最短路徑: {string.Join(" -> ", path)}"); // A -> B -> C -> D
Console.WriteLine($"總權重: {weight}"); // 10 + 5 + 30 = 45