1. 初始設定：
初始化一個陣列 dist[] 用於儲存從起始節點到其他節點的最短距離。一開始，起始節點的最短距離設為 0，其他節點的最短距離設為無窮大。同時，初始化一個陣列 sptSet[] 用於標記哪些節點已經包含在最短路徑樹中。
2. 主循環：
重複以下步驟直到所有節點都被納入最短路徑樹中。
• 找到未包含在最短路徑樹中的節點中，距離起始節點最近的節點（即 dist[] 最小的節點）。設定這個節點為 u。
• 將節點 u 納入最短路徑樹中（即將 sptSet[u] 設為 true）。
• 更新 dist[] 陣列，檢查通過節點 u 是否可以縮短其他節點到起始節點的距離。
3. 重複：
重複步驟 2 直到所有節點都被納入最短路徑樹。

1. 貪心策略：
Dijkstra 演算法使用貪心策略，每次選擇當前最短距離的節點進行擴展。這確保了在每個步驟中都選擇了最優解，並最終得到整體最優解。
2. 非負權重：
Dijkstra 演算法要求所有邊的權重都是非負的。這是因為該演算法的基本原理是通過不斷擴展最短的路徑，如果有負權重，這種策略可能不再有效，甚至會導致錯誤的結果。
3. 遞推：
Dijkstra 演算法通過遞推的方式計算最短路徑，每一步都確保了目前的最短路徑是全局最短。
4. 時間複雜度：
使用最小堆（Min Heap）實現 Dijkstra 演算法的時間複雜度為 O((V + E) * log(V))，其中 V 是節點數量，E 是邊的數量。

using System;
class ShortestPathAlgorithm
{
    const int V = 5; // 節點數量
    const int NoPath = -1;//無路徑
    /// <summary>
    /// 選擇未包含在最短路徑樹中，距離最短的節點
    /// </summary>
    /// <param name="dist">起點至各點的最短距離</param>
    /// <param name="sptSet">已經拜訪過的點旗標</param>
    /// <returns>傳回 索引值，起點至索引點為目前最短距離(扣除已拜訪過的點)</returns>
    int MinDistance(int[] dist, bool[] sptSet)
    {
        int min = int.MaxValue, minIndex = NoPath;
        for (int v = 0; v < V; v++)
        {
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                minIndex = v;
            }
        }
        return minIndex;
    }

    /// <summary>
    /// 輸出起點到 dest 的最短路徑
    /// </summary>
    /// <param name="dist">起點至各點的最短距離</param>
    /// <param name="parent">最短路徑連結</param>
    /// <param name="dest">目標點</param>
    void PrintSolution(int[] dist, int[] parent, int dest)
    {
        Stack <int> St = new Stack<int>();
        Console.Write($"到節點 {dest} 的最短路徑:");
        int i = dest;
        while (parent[i] != NoPath) St.Push(i = parent[i]);
        Console.Write(St.Pop());
        while (St.Count > 0) Console.Write($" -> {St.Pop()}");
        Console.WriteLine($" -> {dest} = {dist[dest]}");
    }

    /// <summary>
    /// Dijkstra 最短路徑
    /// </summary>
    /// <param name="graph">地圖陣列</param>
    /// <param name="src">起點</param>
    /// <param name="dest">終點</param>
    void Dijkstra(int[][] graph, int src, int dest)
    {
        // 初始化起始點至各點最短距離為無窮大，最短路徑已拜訪標記為 false，父節點為 NoPath
        int[] dist = Enumerable.Repeat(int.MaxValue, V).ToArray();//距離
        bool[] sptSet = Enumerable.Repeat(false, V).ToArray();//父節點
        int[] parent = Enumerable.Repeat(NoPath, V).ToArray();//最短路徑標記
        dist[src] = 0; // 起始節點到 src 自身的距離為 0
        for (int count = 0; count < V - 1; count++) // 主循環，找到最短路徑
        {
            int u = MinDistance(dist, sptSet); // 選擇未包含在最短路徑樹中，距離最短的節點
            sptSet[u] = true; // 將選定的節點標記為已納入最短路徑樹
            for (int v = 0; v < V; v++) // 更新相鄰節點的最短距離
            {
                // 檢查節點是否未包含在最短路徑樹中，是否有邊相連，是否有更短的距離
                if (!sptSet[v] && graph[u][v] != NoPath && dist[u] != int.MaxValue && dist[u] + graph[u][v] < dist[v])
                {
                    dist[v] = dist[u] + graph[u][v]; //更新最短距離及父節點
                    parent[v] = u; //更新到 v 節點的路徑是從 u 點而來
                }
            }
        }
        PrintSolution(dist, parent, dest); //輸出最短距離及路徑
    }

    static void Main()
    {
        int[][] path = new int[][] //地圖路徑距離
        {
            new int[] {0, NoPath, 14, 3, 12},
            new int[] {6, 0, NoPath, 5, 6},
            new int[] {NoPath, 4, 0, 4, 2},
            new int[] {5, 8, 4, 0, NoPath},
            new int[] {NoPath, NoPath, 4, NoPath, 0}
        };
        ShortestPathAlgorithm x = new ShortestPathAlgorithm(); //x 為最短路徑物件
        Console.Write("輸入起始節點 (source): "); int source = int.Parse(Console.ReadLine());
        Console.Write("輸入目標節點 (destination): "); int destination = int.Parse(Console.ReadLine());
        if(source != destination) x.Dijkstra(path, source, destination);
    }
}