C#最短路径算法代码
时间: 2023-11-23 17:52:57 浏览: 49
C#中实现最短路径算法的方式有很多种,其中比较常用的是Dijkstra算法和A*算法。下面我给你介绍一下这两种算法的实现方式。
1. Dijkstra算法
Dijkstra算法是一种经典的最短路径算法,它可以求解带权有向图中的单源最短路径问题。具体实现步骤如下:
(1)初始化:将起点s加入集合S,将所有与s直接相连的点加入集合T。
(2)选择最短路径:从T中选择一个到s距离最短的点v,并将v加入集合S。
(3)更新距离:对于T中的每个点w,如果从s到v再到w的距离比从s到w的距离更短,则更新从s到w的距离。
(4)重复执行步骤2和步骤3,直到T为空。
下面是C#代码实现:
```
public 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 = -1;
for (int i = 0; i < n; i++)
{
if (!visited[i] && (u == -1 || dist[i] < dist[u]))
{
u = i;
}
}
visited[u] = true;
for (int v = 0; v < n; v++)
{
if (graph[u, v] != 0 && !visited[v])
{
int alt = dist[u] + graph[u, v];
if (alt < dist[v])
{
dist[v] = alt;
}
}
}
}
}
```
2. A*算法
A*算法是一种启发式搜索算法,它可以在带权有向图中找到从起点到终点的最短路径。具体实现步骤如下:
(1)初始化:将起点加入open列表,将起点的f值设为0。
(2)选择节点:从open列表中选择f值最小的节点作为当前节点,并将其从open列表中移除,加入close列表。
(3)扩展节点:对于当前节点的每个邻居节点,计算其g值和h值,并计算出f值。如果该节点不在open列表和close列表中,则将其加入open列表。
(4)重复执行步骤2和步骤3,直到当前节点为终点或者open列表为空。
下面是C#代码实现:
```
public static void AStar(int[,] graph, int start, int end)
{
int n = graph.GetLength(0);
int[] g = new int[n];
int[] h = new int[n];
int[] f = new int[n];
int[] parent = new int[n];
bool[] open = new bool[n];
bool[] close = new bool[n];
for (int i = 0; i < n; i++)
{
g[i] = int.MaxValue;
h[i] = Heuristic(graph, i, end);
f[i] = int.MaxValue;
parent[i] = -1;
open[i] = false;
close[i] = false;
}
g[start] = 0;
f[start] = h[start];
open[start] = true;
while (true)
{
int u = -1;
for (int i = 0; i < n; i++)
{
if (open[i] && (u == -1 || f[i] < f[u]))
{
u = i;
}
}
if (u == -1)
{
break;
}
if (u == end)
{
break;
}
open[u] = false;
close[u] = true;
for (int v = 0; v < n; v++)
{
if (graph[u, v] != 0 && !close[v])
{
int alt = g[u] + graph[u, v];
if (alt < g[v])
{
g[v] = alt;
f[v] = g[v] + h[v];
parent[v] = u;
if (!open[v])
{
open[v] = true;
}
}
}
}
}
}
private static int Heuristic(int[,] graph, int start, int end)
{
return Math.Abs(start / graph.GetLength(1) - end / graph.GetLength(1)) + Math.Abs(start % graph.GetLength(1) - end % graph.GetLength(1));
}
```