当前位置：首页 > news >正文

C# 路径算法之Dijkstra算法

news 2024/9/23 10:11:11

Dijkstra算法是一种用于在图中找到从单个源节点到其他所有节点的最短路径的算法。它适用于带有非负权重的图。在C#中实现Dijkstra算法，我们可以使用优先队列（如SortedDictionary或SortedSet与自定义比较器，或者使用.NET的PriorityQueue类，如果你使用的是较新版本的.NET）来优化性能。但为了简化说明，这里我将使用一个简单的List和一个MinHeap的模拟来实现它。

然而，为了保持示例的清晰和简洁，我将使用一个基于List和for循环的简化版本，尽管这不是最高效的实现。

以下是Dijkstra算法的一个C#实现示例：

using System;
using System.Collections.Generic;
using System.Linq;class Graph
{private Dictionary<int, List<Edge>> adjList;public Graph(int numVertices){adjList = new Dictionary<int, List<Edge>>(numVertices);for (int i = 0; i < numVertices; i++){adjList[i] = new List<Edge>();}}public void AddEdge(int src, int dest, int weight){adjList[src].Add(new Edge(dest, weight));}public Dictionary<int, int> Dijkstra(int src){int numVertices = adjList.Count;var dist = new Dictionary<int, int>(numVertices);var visited = new HashSet<int>();// 初始化距离数组，所有距离为无穷大，除了源节点为0foreach (var vertex in adjList.Keys){dist[vertex] = int.MaxValue;}dist[src] = 0;// 找到最短路径for (int count = 0; count < numVertices - 1; count++){// 选择最小距离的未访问节点int u = GetMinDistanceVertex(dist, visited);// 标记节点为已访问visited.Add(u);// 更新相邻节点的距离foreach (var neighbor in adjList[u]){int v = neighbor.Dest;int weight = neighbor.Weight;if (!visited.Contains(v) && dist[u] != int.MaxValue && dist[u] + weight < dist[v]){dist[v] = dist[u] + weight;}}}return dist;}// 辅助函数，用于从未访问的节点中找到距离最小的节点private int GetMinDistanceVertex(Dictionary<int, int> dist, HashSet<int> visited){int min = int.MaxValue;int minIndex = -1;foreach (var vertex in dist.Keys){if (!visited.Contains(vertex) && dist[vertex] <= min){min = dist[vertex];minIndex = vertex;}}return minIndex;}// 边的结构体struct Edge{public int Dest;public int Weight;public Edge(int dest, int weight){Dest = dest;Weight = weight;}}
}class Program
{static void Main(string[] args){Graph g = new Graph(5);g.AddEdge(0, 1, 10);g.AddEdge(0, 2, 6);g.AddEdge(0, 3, 5);g.AddEdge(1, 3, 15);g.AddEdge(2, 3, 4);var distances = g.Dijkstra(0);foreach (var kvp in distances){Console.WriteLine($"Distance from 0 to {kvp.Key} is {kvp.Value}");}}
}