C# で最短パス アルゴリズムを実装する方法

C# で最短パス アルゴリズムを実装するには、特定のコード サンプルが必要です。

最短パス アルゴリズムは、グラフ理論の重要なアルゴリズムであり、グラフを解くために使用されます。 2 つの頂点間のパス。この記事では、C# 言語を使用して 2 つの古典的な最短経路アルゴリズム、ダイクストラ アルゴリズムとベルマン フォード アルゴリズムを実装する方法を紹介します。

ダイクストラのアルゴリズムは、広く使用されている単一ソースの最短パス アルゴリズムです。その基本的な考え方は、開始頂点から開始して、徐々に他のノードに拡張し、発見されたノードの最短パスを更新することです。以下は、ダイクストラのアルゴリズムを使用して最短経路を解くサンプル コードです。

using System;
using System.Collections.Generic;

public class DijkstraAlgorithm
{
    private int vertexCount;
    private int[] distance;
    private bool[] visited;
    private List<List<int>> adjacencyMatrix;

    public DijkstraAlgorithm(List<List<int>> graph)
    {
        vertexCount = graph.Count;
        distance = new int[vertexCount];
        visited = new bool[vertexCount];
        adjacencyMatrix = graph;
    }

    public void FindShortestPath(int startVertex)
    {
        // 初始化距离数组和访问数组
        for (int i = 0; i < vertexCount; i++)
        {
            distance[i] = int.MaxValue;
            visited[i] = false;
        }

        // 起始顶点到自身的距离为0
        distance[startVertex] = 0;

        for (int i = 0; i < vertexCount - 1; i++)
        {
            int u = FindMinDistance();

            // 标记u为已访问
            visited[u] = true;

            // 更新u的邻接顶点的距离
            for (int v = 0; v < vertexCount; v++)
            {
                if (!visited[v] && adjacencyMatrix[u][v] != 0 && distance[u] != int.MaxValue
                    && distance[u] + adjacencyMatrix[u][v] < distance[v])
                {
                    distance[v] = distance[u] + adjacencyMatrix[u][v];
                }
            }
        }

        // 输出最短路径
        Console.WriteLine("顶点    最短路径");
        for (int i = 0; i < vertexCount; i++)
        {
            Console.WriteLine(i + "    " + distance[i]);
        }
    }

    private int FindMinDistance()
    {
        int minDistance = int.MaxValue;
        int minDistanceIndex = -1;
        for (int i = 0; i < vertexCount; i++)
        {
            if (!visited[i] && distance[i] <= minDistance)
            {
                minDistance = distance[i];
                minDistanceIndex = i;
            }
        }
        return minDistanceIndex;
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        // 构建示例图
        List<List<int>> graph = new List<List<int>>()
        {
            new List<int>() {0, 4, 0, 0, 0, 0, 0, 8, 0},
            new List<int>() {4, 0, 8, 0, 0, 0, 0, 11, 0},
            new List<int>() {0, 8, 0, 7, 0, 4, 0, 0, 2},
            new List<int>() {0, 0, 7, 0, 9, 14, 0, 0, 0},
            new List<int>() {0, 0, 0, 9, 0, 10, 0, 0, 0},
            new List<int>() {0, 0, 4, 0, 10, 0, 2, 0, 0},
            new List<int>() {0, 0, 0, 14, 0, 2, 0, 1, 6},
            new List<int>() {8, 11, 0, 0, 0, 0, 1, 0, 7},
            new List<int>() {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };

        // 使用Dijkstra算法求解最短路径
        DijkstraAlgorithm dijkstraAlgorithm = new DijkstraAlgorithm(graph);
        dijkstraAlgorithm.FindShortestPath(0);
    }
}

Bellman-Ford アルゴリズムは、負の重みグラフを使用した最短経路問題を解くためのアルゴリズムです。動的プログラミングの考え方を使用して、頂点の最短経路を徐々に更新します。以下は、ベルマン フォード アルゴリズムを使用して最短パスを解決するサンプル コードです。

using System;
using System.Collections.Generic;

public class BellmanFordAlgorithm
{
    private int vertexCount;
    private int[] distance;
    private List<Edge> edges;

    private class Edge
    {
        public int source;
        public int destination;
        public int weight;

        public Edge(int source, int destination, int weight)
        {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }
    }

    public BellmanFordAlgorithm(int vertexCount)
    {
        this.vertexCount = vertexCount;
        distance = new int[vertexCount];
        edges = new List<Edge>();
    }

    public void AddEdge(int source, int destination, int weight)
    {
        edges.Add(new Edge(source, destination, weight));
    }

    public void FindShortestPath(int startVertex)
    {
        // 初始化距离数组
        for (int i = 0; i < vertexCount; i++)
        {
            distance[i] = int.MaxValue;
        }

        // 起始顶点到自身的距离为0
        distance[startVertex] = 0;

        // 迭代vertexCount-1次，更新距离
        for (int i = 0; i < vertexCount - 1; i++)
        {
            foreach (Edge edge in edges)
            {
                if (distance[edge.source] != int.MaxValue && distance[edge.source] + edge.weight < distance[edge.destination])
                {
                    distance[edge.destination] = distance[edge.source] + edge.weight;
                }
            }
        }

        // 检查是否存在负权环路
        foreach (Edge edge in edges)
        {
            if (distance[edge.source] != int.MaxValue && distance[edge.source] + edge.weight < distance[edge.destination])
            {
                Console.WriteLine("图中存在负权环路");
                return;
            }
        }

        // 输出最短路径
        Console.WriteLine("顶点    最短路径");
        for (int i = 0; i < vertexCount; i++)
        {
            Console.WriteLine(i + "    " + distance[i]);
        }
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        // 构建示例图
        int vertexCount = 5;
        BellmanFordAlgorithm bellmanFordAlgorithm = new BellmanFordAlgorithm(vertexCount);
        bellmanFordAlgorithm.AddEdge(0, 1, 6);
        bellmanFordAlgorithm.AddEdge(0, 2, 7);
        bellmanFordAlgorithm.AddEdge(1, 2, 8);
        bellmanFordAlgorithm.AddEdge(1, 4, -4);
        bellmanFordAlgorithm.AddEdge(1, 3, 5);
        bellmanFordAlgorithm.AddEdge(2, 4, 9);
        bellmanFordAlgorithm.AddEdge(2, 3, -3);
        bellmanFordAlgorithm.AddEdge(3, 1, -2);
        bellmanFordAlgorithm.AddEdge(4, 3, 7);

        // 使用Bellman-Ford算法求解最短路径
        bellmanFordAlgorithm.FindShortestPath(0);
    }
}

上記は、C# 言語を使用してダイクストラ アルゴリズムとベルマン フォード アルゴリズムを実装するサンプル コードです。これら 2 つのアルゴリズムを使用すると、グラフ内の最短経路問題を解決できます。

以上がC# で最短パス アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。