C#代码实现Dijkstra算法

C#代码实现Dijkstra算法的基本步骤如下：
1. 定义一个节点类，包含节点名称、邻接节点、边权重等信息。
2. 定义一个图类，包含节点集合、边集合等信息。
3. 实现Dijkstra算法，首先初始化起点到各个节点的距离为无穷大，起点到自身的距离为0。然后遍历所有节点，找到距离起点最近的节点，并更新其邻接节点的距离。重复此过程直到所有节点都被遍历过。
4. 最后根据起点到各个节点的距离，构建最短路径。

下面是一个简单的C#代码实现Dijkstra算法的例子：

using System;
using System.Collections.Generic;

public class Node
{
    public string Name { get; set; }
    public List<Edge> Edges { get; set; }
    public int Distance { get; set; }
    public bool Visited { get; set; }

    public Node(string name)
    {
        Name = name;
        Edges = new List<Edge>();
        Distance = int.MaxValue;
        Visited = false;
    }
}

public class Edge
{
    public Node Start { get; set; }
    public Node End { get; set; }
    public int Weight { get; set; }

    public Edge(Node start, Node end, int weight)
    {
        Start = start;
        End = end;
        Weight = weight;
    }
}

public class Graph
{
    public List<Node> Nodes { get; set; }
    public List<Edge> Edges { get; set; }

    public Graph()
    {
        Nodes = new List<Node>();
        Edges = new List<Edge>();
    }

    public void AddNode(Node node)
    {
        Nodes.Add(node);
    }

    public void AddEdge(Node start, Node end, int weight)
    {
        Edge edge = new Edge(start, end, weight);
        start.Edges.Add(edge);
        Edges.Add(edge);
    }

    public void Dijkstra(Node start)
    {
        start.Distance = 0;
        Node current = start;

        while (current != null)
        {
            current.Visited = true;

            foreach (Edge edge in current.Edges)
            {
                Node neighbor = edge.End;

                if (!neighbor.Visited)
                {
                    int distance = current.Distance + edge.Weight;

                    if (distance < neighbor.Distance)
                    {
                        neighbor.Distance = distance;
                    }
                }
            }

            current = null;
            int shortestDistance = int.MaxValue;

            foreach (Node node in Nodes)
            {
                if (!node.Visited && node.Distance < shortestDistance)
                {
                    shortestDistance = node.Distance;
                    current = node;
                }
            }
        }
    }

    public List<Node> GetShortestPath(Node start, Node end)
    {
        List<Node> path = new List<Node>();
        Node current = end;

        while (current != start)
        {
            path.Insert(0, current);

            foreach (Edge edge in current.Edges)
            {
                Node neighbor = edge.End;

                if (current.Distance == neighbor.Distance + edge.Weight)
                {
                    current = neighbor;
                    break;
                }
            }
        }

        path.Insert(0, start);
        return path;
    }
}

// 使用示例
Graph graph = new Graph();

Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");

graph.AddNode(a);
graph.AddNode(b);
graph.AddNode(c);
graph.AddNode(d);
graph.AddNode(e);

graph.AddEdge(a, b, 5);
graph.AddEdge(a, c, 3);
graph.AddEdge(b, c, 1);
graph.AddEdge(b, d, 2);
graph.AddEdge(c, d, 4);
graph.AddEdge(d, e, 6);

graph.Dijkstra(a);

List<Node> path = graph.GetShortestPath(a, e);

foreach (Node node in path)
{
    Console.Write(node.Name + " ");
}

// 输出结果为：A C B D E

--相关问题--: