需求:自己写一套简单导航逻辑。1.导航路径由一个个节点组成,每个节点自定义可到达哪几个节点,根据这样一个网络写出一套算法实时获取最近节点,然后计算出所有可能到达终点的方案中最近的方案,最后返回出最近方案的数组,用c#写
时间: 2023-12-17 08:05:35 浏览: 31
好的,我可以为您提供一种基于Dijkstra算法的简单导航逻辑。以下是实现步骤:
1.定义节点类
首先,我们需要定义一个节点类,该类包含节点的ID、节点的邻居节点和到邻居节点的距离等信息。代码如下:
```csharp
class Node
{
public int Id { get; set; }
public Dictionary<Node, int> Neighbors { get; set; }
public int Distance { get; set; }
public Node(int id)
{
Id = id;
Neighbors = new Dictionary<Node, int>();
Distance = int.MaxValue;
}
}
```
2.构建节点网络
然后,我们需要构建一个节点网络,即将所有节点连接起来。这里为了演示方便,我们手动创建一个简单的节点网络。代码如下:
```csharp
// 创建节点
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
// 添加邻居节点和距离
n1.Neighbors.Add(n2, 7);
n1.Neighbors.Add(n3, 9);
n1.Neighbors.Add(n6, 14);
n2.Neighbors.Add(n1, 7);
n2.Neighbors.Add(n3, 10);
n2.Neighbors.Add(n4, 15);
n3.Neighbors.Add(n1, 9);
n3.Neighbors.Add(n2, 10);
n3.Neighbors.Add(n4, 11);
n3.Neighbors.Add(n6, 2);
n4.Neighbors.Add(n2, 15);
n4.Neighbors.Add(n3, 11);
n4.Neighbors.Add(n5, 6);
n5.Neighbors.Add(n4, 6);
n5.Neighbors.Add(n6, 9);
n6.Neighbors.Add(n1, 14);
n6.Neighbors.Add(n3, 2);
n6.Neighbors.Add(n5, 9);
```
3.实现Dijkstra算法
接下来,我们可以实现Dijkstra算法来查找最近的节点。Dijkstra算法是一种贪心算法,它从起点开始,依次遍历所有节点,并计算起点到每个节点的距离。同时,它记录下每个节点的前一个节点,以便后面计算最短路径。代码如下:
```csharp
private static List<Node> Dijkstra(Node start, Node end)
{
List<Node> result = new List<Node>();
// 初始化节点距离为无穷大
foreach (var node in new List<Node>() { start, end })
{
node.Distance = int.MaxValue;
}
// 初始化起点距离为0
start.Distance = 0;
// 待访问节点队列
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(start);
// 访问过的节点集合
HashSet<Node> visited = new HashSet<Node>();
// 记录每个节点的前一个节点
Dictionary<Node, Node> previous = new Dictionary<Node, Node>();
while (queue.Any())
{
// 取出队列中的第一个节点
Node current = queue.Dequeue();
// 记录已访问节点
visited.Add(current);
// 遍历邻居节点
foreach (var neighbor in current.Neighbors)
{
var node = neighbor.Key;
var distance = neighbor.Value;
// 如果邻居节点已访问,则跳过
if (visited.Contains(node)) continue;
// 计算起点到邻居节点的距离
int tentativeDistance = current.Distance + distance;
// 如果计算出的距离比当前记录的距离小,则更新距离和前一个节点
if (tentativeDistance < node.Distance)
{
node.Distance = tentativeDistance;
previous[node] = current;
// 将节点加入待访问队列
queue.Enqueue(node);
}
}
// 如果已遍历到终点,则跳出循环
if (current == end) break;
}
// 计算最短路径
if (previous.ContainsKey(end))
{
Node node = end;
while (node != null)
{
result.Insert(0, node);
node = previous.ContainsKey(node) ? previous[node] : null;
}
}
return result;
}
```
4.获取最短路径
最后,我们可以调用Dijkstra算法来获取最短路径。这里我们假设起点为节点n1,终点为节点n5。代码如下:
```csharp
// 获取最短路径
List<Node> shortestPath = Dijkstra(n1, n5);
// 输出最短路径
if (shortestPath.Any())
{
Console.WriteLine("Shortest path:");
foreach (var node in shortestPath)
{
Console.Write(node.Id + " ");
}
}
else
{
Console.WriteLine("No path found.");
}
```
完整代码如下:
```csharp
using System;
using System.Collections.Generic;
using System.Linq;
class Node
{
public int Id { get; set; }
public Dictionary<Node, int> Neighbors { get; set; }
public int Distance { get; set; }
public Node(int id)
{
Id = id;
Neighbors = new Dictionary<Node, int>();
Distance = int.MaxValue;
}
}
class Program
{
private static List<Node> Dijkstra(Node start, Node end)
{
List<Node> result = new List<Node>();
// 初始化节点距离为无穷大
foreach (var node in new List<Node>() { start, end })
{
node.Distance = int.MaxValue;
}
// 初始化起点距离为0
start.Distance = 0;
// 待访问节点队列
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(start);
// 访问过的节点集合
HashSet<Node> visited = new HashSet<Node>();
// 记录每个节点的前一个节点
Dictionary<Node, Node> previous = new Dictionary<Node, Node>();
while (queue.Any())
{
// 取出队列中的第一个节点
Node current = queue.Dequeue();
// 记录已访问节点
visited.Add(current);
// 遍历邻居节点
foreach (var neighbor in current.Neighbors)
{
var node = neighbor.Key;
var distance = neighbor.Value;
// 如果邻居节点已访问,则跳过
if (visited.Contains(node)) continue;
// 计算起点到邻居节点的距离
int tentativeDistance = current.Distance + distance;
// 如果计算出的距离比当前记录的距离小,则更新距离和前一个节点
if (tentativeDistance < node.Distance)
{
node.Distance = tentativeDistance;
previous[node] = current;
// 将节点加入待访问队列
queue.Enqueue(node);
}
}
// 如果已遍历到终点,则跳出循环
if (current == end) break;
}
// 计算最短路径
if (previous.ContainsKey(end))
{
Node node = end;
while (node != null)
{
result.Insert(0, node);
node = previous.ContainsKey(node) ? previous[node] : null;
}
}
return result;
}
static void Main(string[] args)
{
// 创建节点
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
// 添加邻居节点和距离
n1.Neighbors.Add(n2, 7);
n1.Neighbors.Add(n3, 9);
n1.Neighbors.Add(n6, 14);
n2.Neighbors.Add(n1, 7);
n2.Neighbors.Add(n3, 10);
n2.Neighbors.Add(n4, 15);
n3.Neighbors.Add(n1, 9);
n3.Neighbors.Add(n2, 10);
n3.Neighbors.Add(n4, 11);
n3.Neighbors.Add(n6, 2);
n4.Neighbors.Add(n2, 15);
n4.Neighbors.Add(n3, 11);
n4.Neighbors.Add(n5, 6);
n5.Neighbors.Add(n4, 6);
n5.Neighbors.Add(n6, 9);
n6.Neighbors.Add(n1, 14);
n6.Neighbors.Add(n3, 2);
n6.Neighbors.Add(n5, 9);
// 获取最短路径
List<Node> shortestPath = Dijkstra(n1, n5);
// 输出最短路径
if (shortestPath.Any())
{
Console.WriteLine("Shortest path:");
foreach (var node in shortestPath)
{
Console.Write(node.Id + " ");
}
}
else
{
Console.WriteLine("No path found.");
}
Console.ReadLine();
}
}
```