Dijkstra算法用c#实现

以下是使用C#实现Dijkstra算法的示例代码：

using System;
using System.Collections.Generic;

public class DijkstraAlgorithm
{
    private int V; // 图中顶点的数量

    public DijkstraAlgorithm(int v)
    {
        V = v;
    }

    // 找到最短路径的顶点
    private int MinDistance(int[] dist, bool[] visited)
    {
        int minDistance = int.MaxValue;
        int minIndex = -1;

        for (int i = 0; i < V; i++)
        {
            if (visited[i] == false && dist[i] <= minDistance)
            {
                minDistance = dist[i];
                minIndex = i;
            }
        }

        return minIndex;
    }

    // 打印最短路径
    private void PrintPath(int[] parent, int destination)
    {
        if (parent[destination] == -1)
            return;

        PrintPath(parent, parent[destination]);
        Console.Write(destination + " ");
    }

    // 打印最短路径和距离
    public void PrintSolution(int[] dist, int[] parent, int source)
    {
        Console.WriteLine("顶点\t最短路径\t路径");
        for (int i = 0; i < V; i++)
        {
            Console.Write(source + " -> " + i + "\t" + dist[i] + "\t" + source + " ");
            PrintPath(parent, i);
            Console.WriteLine();
        }
    }

    // Dijkstra算法实现
    public void Dijkstra(int[,] graph, int source)
    {
        int[] dist = new int[V]; // 存储最短路径的距离
        bool[] visited = new bool[V]; // 标记顶点是否已被访问
        int[] parent = new int[V]; // 存储最短路径的父节点

        for (int i = 0; i < V; i++)
        {
            dist[i] = int.MaxValue;
            visited[i] = false;
            parent[0] = -1;
        }

        dist[source] = 0;

        for (int count = 0; count < V - 1; count++)
        {
            int u = MinDistance(dist, visited);
            visited[u] = true;

            for (int v = 0; v < V; v++)
            {
                if (!visited[v] && graph[u, v] != 0 && dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v])
                {
                    dist[v] = dist[u] + graph[u, v];
                    parent[v] = u;
                }
            }
        }

        PrintSolution(dist, parent, source);
    }

    // 测试
    public static void Main(string[] args)
    {
        int[,] graph = {
            { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
            { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
            { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
            { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
            { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
            { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
            { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
            { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
            { 0, 0, 2, 0, 0, 0, 6, 7, 0 }
        };

        DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(9);
        dijkstra.Dijkstra(graph, 0);
    }
}

以上代码实现了Dijkstra算法，并提供了一个用于测试的示例图。你可以根据自己的需求修改图的大小和边的权重，并调用`Dijkstra`方法来计算最短路径。最后，通过`PrintSolution`方法打印出每个顶点到源顶点的最短路径和距离。