C# .net 最短路径

C# .NET中有多种实现最短路径算法的方法，其中比较常用的是Dijkstra算法和Floyd Warshall算法。下面分别介绍这两种算法的实现方法：

1. Dijkstra算法

Dijkstra算法是一种贪心算法，用于解决带权图的单源最短路径问题。该算法的基本思想是从起点开始，每次选择当前距离起点最近的一个顶点，然后以该顶点为中心进行扩展，直到扩展到终点为止。具体实现方法如下：

public static int[] Dijkstra(int[,] graph, int source)
{
    int n = graph.GetLength(0);
    int[] dist = new int[n];
    bool[] visited = new bool[n];

    for (int i = 0; i < n; i++)
    {
        dist[i] = int.MaxValue;
        visited[i] = false;
    }

    dist[source] = 0;

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

        for (int v = 0; v < n; 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];
            }
        }
    }

    return dist;
}

private static int MinDistance(int[] dist, bool[] visited)
{
    int min = int.MaxValue;
    int minIndex = -1;

    for (int v = 0; v < dist.Length; v++)
    {
        if (!visited[v] && dist[v] <= min)
        {
            min = dist[v];
            minIndex = v;
        }
    }

    return minIndex;
}

2. Floyd Warshall算法

Floyd Warshall算法是一种动态规划算法，用于解决带权图的所有点对最短路径问题。该算法的基本思想是利用中间顶点的集合逐步扩大，从而求出所有顶点之间的最短路径。具体实现方法如下：

public static int[,] FloydWarshall(int[,] graph)
{
    int n = graph.GetLength(0);
    int[,] dist = new int[n, n];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            dist[i, j] = graph[i, j];
        }
    }

    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (dist[i, k] != int.MaxValue && dist[k, j] != int.MaxValue && dist[i, k] + dist[k, j] < dist[i, j])
                {
                    dist[i, j] = dist[i, k] + dist[k, j];
                }
            }
        }
    }

    return dist;
}