Bagaimana untuk melaksanakan algoritma laluan terpendek dalam C#

Bagaimana untuk melaksanakan algoritma laluan terpendek dalam C#, contoh kod khusus diperlukan

Algoritma laluan terpendek ialah algoritma penting dalam teori graf, digunakan untuk mencari laluan terpendek antara dua bucu dalam graf. Dalam artikel ini, kami akan memperkenalkan cara menggunakan bahasa C# untuk melaksanakan dua algoritma laluan terpendek klasik: algoritma Dijkstra dan algoritma Bellman-Ford.

Algoritma Dijkstra ialah algoritma laluan terpendek sumber tunggal yang digunakan secara meluas. Idea asasnya ialah bermula dari puncak permulaan, berkembang secara beransur-ansur ke nod lain, dan mengemas kini laluan terpendek bagi nod yang ditemui. Berikut ialah kod sampel yang menggunakan algoritma Dijkstra untuk menyelesaikan laluan terpendek:

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);
    }
}

Algoritma Bellman-Ford ialah algoritma untuk menyelesaikan masalah laluan terpendek dengan graf berat negatif. Ia menggunakan idea pengaturcaraan dinamik untuk mengemas kini laluan terpendek simpang secara beransur-ansur. Berikut ialah contoh kod yang menggunakan algoritma Bellman-Ford untuk menyelesaikan laluan terpendek:

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);
    }
}

Di atas adalah contoh kod yang menggunakan bahasa C# untuk melaksanakan algoritma Dijkstra dan algoritma Bellman-Ford. Melalui kedua-dua algoritma ini, kita boleh menyelesaikan masalah laluan terpendek dalam graf.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma laluan terpendek dalam C#. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!