最短距離法c#

"最短距離法"（Shortest Path Algorithm）是計算機科學中用於查找圖（graph）中兩點之間最短路徑的算法。在C#中，你可以使用多種算法來實現最短路徑查找，包括：

1. 迪傑斯特拉算法（Dijkstra's Algorithm）
2. 弗洛伊德算法（Floyd-Warshall Algorithm）
3. 貝爾曼-福特算法（Bellman-Ford Algorithm）
4. A*算法

下面是一個簡單的例子，展示了如何使用迪傑斯特拉算法來查找最短路徑。這個例子假設有一個有向圖，它的頂點表示城市，邊的權重表示城市之間的距離。

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 頂點數
        int V = 9;
        // 頂點之間的距離
        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}
        };

        // 頂點源
        int source = 0;

        // 迪傑斯特拉算法
        Dictionary<int, int>[] graphDistances = Dijkstra(V, graph, source);

        // 列印最短路徑
        PrintShortestPaths(graphDistances, V, source);
    }

    static Dictionary<int, int>[] Dijkstra(int V, int[,] graph, int source)
    {
        // 創建距離表
        Dictionary<int, int>[] distances = new Dictionary<int, int>[V];
        for (int v = 0; v < V; v++)
            distances[v] = new Dictionary<int, int>();

        // 創建堆疊來存儲頂點
        Stack<int> stack = new Stack<int>();

        // 初始化源頂點
        distances[source][source] = 0;

        // 開始搜尋
        while (stack.Count < V)
        {
            // 找到未訪問且距離最小的頂點
            int u = GetMinDistanceVertex(distances, V);

            // 如果所有頂點都已訪問過，退出循環
            if (u == -1)
                break;

            // 訪問頂點u
            stack.Push(u);

            // 更新u的鄰居頂點的距離
            foreach (int v in GetNeighbors(graph, u))
            {
                int weight = graph[u, v];
                if (distances[u].ContainsKey(v) && distances[u][v] + weight < distances[v][v])
                {
                    distances[u][v] = distances[v][v] = distances[u][v] + weight;
                }
            }
        }

        return distances;
    }

    static int GetMinDistanceVertex(Dictionary<int, int>[] distances, int V)
    {
        // 創建一個臨時數組來存儲頂點及其距離
        int[] distancesArray = new int[V];
        for (int v = 0; v < V; v++)
        {
            if (distances[v].Count > 0)
                distancesArray[v] = distances[v][v];
            else
                distancesArray[v] = int.MaxValue;
        }

        // 返回最小距離的頂點
        return Array.IndexOf(distancesArray, Math.Min(distancesArray));
    }

    static List<int> GetNeighbors(int[,] graph, int v)
    {
        List<int> neighbors = new List<int>();
        for (int i = 0; i < graph.GetLength(1); i++)
        {
            if (graph[v, i] != 0)
                neighbors.Add(i);
        }
        return neighbors;
    }

    static void PrintShortestPaths(Dictionary<int, int>[] distances, int V, int source)
    {
        for (int v = 0; v < V; v++)
        {
            if (distances[v].ContainsKey(v))
                Console.WriteLine("The distance from {0} to {1} is {2}", source, v, distances[v][v]);
            else
                Console.WriteLine("There is no path from {0} to {1}", source, v);
        }
    }
}

這個例子展示了如何使用迪傑斯特拉算法來查找從一個給定的源頂點到其他所有頂點的最短路徑。在實際套用中，你可能需要根據你的圖的特性選擇合適的算法，並可能需要處理更複雜的情況，比如負權重邊或無權圖。