Comment implémenter l'algorithme du chemin le plus court en C#

Comment implémenter l'algorithme du chemin le plus court en C#, des exemples de code spécifiques sont nécessaires

L'algorithme du chemin le plus court est un algorithme important en théorie des graphes, utilisé pour trouver le chemin le plus court entre deux sommets dans un graphe. Dans cet article, nous présenterons comment utiliser le langage C# pour implémenter deux algorithmes classiques du chemin le plus court : l'algorithme de Dijkstra et l'algorithme de Bellman-Ford.

L'algorithme de Dijkstra est un algorithme de chemin le plus court à source unique largement utilisé. Son idée de base est de partir du sommet de départ, de s'étendre progressivement à d'autres nœuds et de mettre à jour le chemin le plus court des nœuds découverts. Vous trouverez ci-dessous un exemple de code qui utilise l'algorithme de Dijkstra pour résoudre le chemin le plus court :

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

L'algorithme Bellman-Ford est un algorithme permettant de résoudre le problème du chemin le plus court avec des graphiques de poids négatifs. Il utilise l'idée de programmation dynamique pour mettre à jour progressivement le chemin le plus court des sommets. Voici un exemple de code qui utilise l'algorithme de Bellman-Ford pour résoudre le chemin le plus court :

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

Ce qui précède est un exemple de code qui utilise le langage C# pour implémenter l'algorithme de Dijkstra et l'algorithme de Bellman-Ford. Avec ces deux algorithmes, nous pouvons résoudre le problème du chemin le plus court dans le graphe.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!