So implementieren Sie den Kürzeste-Pfad-Algorithmus in C#

Um den Kürzeste-Pfad-Algorithmus in C# zu implementieren, sind spezifische Codebeispiele erforderlich

Der Kürzeste-Pfad-Algorithmus ist ein wichtiger Algorithmus in der Graphentheorie, der verwendet wird, um den kürzesten Pfad zwischen zwei Scheitelpunkten in einem Diagramm zu finden. In diesem Artikel stellen wir vor, wie man die C#-Sprache verwendet, um zwei klassische Algorithmen für den kürzesten Weg zu implementieren: den Dijkstra-Algorithmus und den Bellman-Ford-Algorithmus.

Dijkstras Algorithmus ist ein weit verbreiteter Single-Source-Shortest-Path-Algorithmus. Seine Grundidee besteht darin, vom Startscheitelpunkt aus zu beginnen, sich schrittweise auf andere Knoten auszudehnen und den kürzesten Pfad der erkannten Knoten zu aktualisieren. Unten finden Sie einen Beispielcode, der den Dijkstra-Algorithmus verwendet, um den kürzesten Weg zu lösen:

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

Der Bellman-Ford-Algorithmus ist ein Algorithmus zur Lösung des Problems des kürzesten Wegs mit Diagrammen mit negativem Gewicht. Es nutzt die Idee der dynamischen Programmierung, um den kürzesten Pfad der Scheitelpunkte schrittweise zu aktualisieren. Das Folgende ist ein Beispielcode, der den Bellman-Ford-Algorithmus verwendet, um den kürzesten Weg zu lösen:

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

Das Obige ist ein Beispielcode, der die C#-Sprache verwendet, um den Dijkstra-Algorithmus und den Bellman-Ford-Algorithmus zu implementieren. Mit diesen beiden Algorithmen können wir das Problem des kürzesten Pfades im Diagramm lösen.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Kürzeste-Pfad-Algorithmus in C#. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!