Dijkstra算法的实现

Dijkstra算法是一种用于寻找图中最短路径的贪心算法，它在计算机科学中广泛应用，特别是在路由选择、网络分析和地图导航等领域。下面是Dijkstra算法的基本步骤：

1. 初始化：从起始节点开始（通常称为源或起点），将其标记为已访问，并赋予其距离0。其他所有节点的距离初始化为无穷大。

2. 选择最小距离节点：从未访问过的节点中找到距离当前已知最短距离最小的那个节点。

3. 更新邻接节点距离：对于选定的节点，检查所有相邻节点。如果通过该节点到达邻接节点的距离小于当前记录的距离，更新邻接节点的距离，并标记为已访问。

4. 重复步骤2和3：继续选择并更新直到所有节点都被访问过，或者找到目标节点。

5. 最终结果：返回目标节点的最短路径。

以下是一个简单的C#实现，使用优先队列（`PriorityQueue`）来优化查找过程：

using System.Collections.Generic;
using System.Linq;

public class DijkstraShortestPath
{
    public List<int> GetShortestPaths(int[,] graph, int source)
    {
        int n = graph.GetLength(0);
        bool[] visited = new bool[n];
        int[] distances = Enumerable.Repeat(int.MaxValue, n).ToArray();
        distances[source] = 0;

        var pq = new PriorityQueue<int, (int, int)>((a, b) => a.CompareTo(b));
        pq.Enqueue(source, (distances[source], source));

        while (!pq.IsEmpty())
        {
            int u = pq.Dequeue().Item2;
            if (visited[u]) continue;

            visited[u] = true;

            for (int v = 0; v < n; v++)
            {
                if (!visited[v] && graph[u, v] != 0 &&
                    distances[u] + graph[u, v] < distances[v])
                {
                    distances[v] = distances[u] + graph[u, v];
                    pq.Enqueue(distances[v], v);
                }
            }
        }

        return distances.ToList();
    }
}

class Program
{
    static void Main(string[] args)
    {
        // 假设graph是一个二维数组表示邻接矩阵，source是起始节点
        int[,] graph = ...;
        int source = ...;
        DijkstraShortestPath dijkstra = new DijkstraShortestPath();
        var shortestDistances = dijkstra.GetShortestPaths(graph, source);
        ...
    }
}