c# 最短路径 dijkstra算法
时间: 2023-06-05 19:47:09 浏览: 89
C# 最短路径 Dijkstra算法是一种用于寻找图中最短路径的算法。它基于贪心策略,每次选择当前距离起点最近的节点,并更新与该节点相邻的节点的距离。该算法的时间复杂度为O(n^2),其中n为节点数。
具体实现时,可以使用一个数组来记录每个节点的距离和是否已经被访问过。首先将起点的距离设为0,其余节点的距离设为无穷大。然后从起点开始,每次选择距离起点最近的未访问节点,并更新与该节点相邻的节点的距离。重复该过程直到所有节点都被访问过或者无法到达终点。
以下是C#实现Dijkstra算法的示例代码:
```
using System;
using System.Collections.Generic;
class DijkstraAlgorithm
{
static void Main(string[] args)
{
int[,] graph = new int[,] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
Dijkstra(graph, 0);
}
static void Dijkstra(int[,] graph, int start)
{
int n = graph.GetLength(0);
int[] dist = new int[n];
bool[] visited = new bool[n];
for (int i = 0; i < n; i++)
{
dist[i] = int.MaxValue;
visited[i] = false;
}
dist[start] = 0;
for (int count = 0; count < n - 1; count++)
{
int u = MinDistance(dist, visited);
visited[u] = true;
for (int v = 0; v < n; v++)
{
if (!visited[v] && graph[u, v] != 0 && dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v])
{
dist[v] = dist[u] + graph[u, v];
}
}
}
PrintSolution(dist);
}
static int MinDistance(int[] dist, bool[] visited)
{
int min = int.MaxValue;
int minIndex = -1;
for (int i = 0; i < dist.Length; i++)
{
if (!visited[i] && dist[i] <= min)
{
min = dist[i];
minIndex = i;
}
}
return minIndex;
}
static void PrintSolution(int[] dist)
{
Console.WriteLine("Vertex \t Distance from Source");
for (int i = 0; i < dist.Length; i++)
{
Console.WriteLine(i + " \t\t " + dist[i]);
}
}
}
```
该代码实现了一个简单的Dijkstra算法,用于寻找从起点0到其他节点的最短路径。其中,graph数组表示图的邻接矩阵,dist数组记录每个节点到起点的距离,visited数组记录每个节点是否已经被访问过。在Dijkstra函数中,首先初始化dist和visited数组,然后从起点开始,每次选择距离起点最近的未访问节点,并更新与该节点相邻的节点的距离。最后输出每个节点到起点的最短距离。