C#最短路径算法详解（负权边处理与Bellman-Ford实战指南）

C# 实现 Bellman-Ford 算法

下面我们用 C# 编写一个完整的 Bellman-Ford 算法实现，支持负权边检测和负权环判断。

using System;using System.Collections.Generic;class Edge{    public int Source { get; set; }    public int Destination { get; set; }    public int Weight { get; set; }}class Graph{    public int Vertices { get; set; }    public List<Edge> Edges { get; set; }    public Graph(int vertices)    {        Vertices = vertices;        Edges = new List<Edge>();    }    public void AddEdge(int src, int dest, int weight)    {        Edges.Add(new Edge { Source = src, Destination = dest, Weight = weight });    }}class BellmanFordAlgorithm{    public static void FindShortestPaths(Graph graph, int source)    {        int V = graph.Vertices;        int[] distance = new int[V];        // 初始化距离数组        for (int i = 0; i < V; i++)            distance[i] = int.MaxValue;        distance[source] = 0;        // 松弛所有边 V-1 次        for (int i = 1; i <= V - 1; i++)        {            foreach (var edge in graph.Edges)            {                int u = edge.Source;                int v = edge.Destination;                int w = edge.Weight;                if (distance[u] != int.MaxValue && distance[u] + w < distance[v])                    distance[v] = distance[u] + w;            }        }        // 检查是否存在负权环        bool hasNegativeCycle = false;        foreach (var edge in graph.Edges)        {            int u = edge.Source;            int v = edge.Destination;            int w = edge.Weight;            if (distance[u] != int.MaxValue && distance[u] + w < distance[v])            {                hasNegativeCycle = true;                break;            }        }        if (hasNegativeCycle)        {            Console.WriteLine("图中存在负权环，无法计算最短路径！");            return;        }        // 输出结果        Console.WriteLine("顶点\t距离");        for (int i = 0; i < V; i++)        {            Console.WriteLine($"{i}\t{(distance[i] == int.MaxValue ? "∞" : distance[i].ToString())}");        }    }}// 使用示例class Program{    static void Main()    {        Graph g = new Graph(5);        g.AddEdge(0, 1, -1);        g.AddEdge(0, 2, 4);        g.AddEdge(1, 2, 3);        g.AddEdge(1, 3, 2);        g.AddEdge(1, 4, 2);        g.AddEdge(3, 2, 5);        g.AddEdge(3, 1, 1);        g.AddEdge(4, 3, -3);        BellmanFordAlgorithm.FindShortestPaths(g, 0);    }}

关键点解析

• 初始化：起点距离设为 0，其余设为无穷大（int.MaxValue）。
• 松弛操作：对每条边 (u, v, w)，若 dist[u] + w < dist[v]，则更新 dist[v]。
• 负权环检测：执行 V-1 轮后，若还能松弛，则存在负权环。

应用场景与局限性

Bellman-Ford 算法适用于需要处理 负权边处理 的场景，如金融套利检测、网络延迟优化等。但其时间复杂度为 O(VE)，比 Dijkstra 的 O((V+E)logV) 慢，因此仅在必要时使用。

总结

通过本教程，你已经掌握了如何在 C# 中实现 Bellman-Ford 算法来处理包含负权边的图。这是学习 C#图算法教程 中的重要一环。记住：当图中可能存在负权边时，优先考虑 Bellman-Ford 或其优化版本 SPFA，而不是 Dijkstra。

关键词回顾：C#最短路径算法、负权边处理、Bellman-Ford算法、C#图算法教程。