using RichCreator.Utility.Structs;
|
using System;
|
using System.Collections.Generic;
|
using System.Linq;
|
using System.Text;
|
using System.Threading.Tasks;
|
|
namespace RichCreator.Utility.PathFinding
|
{
|
public class Dijkstra
|
{
|
private List<Node> nodes;
|
private List<Edge> edges;
|
|
public Dijkstra()
|
{
|
nodes = new List<Node>();
|
edges = new List<Edge>();
|
}
|
|
public Dijkstra(List<Tuple<ZTPoint, ZTPoint, double>> edges)
|
{
|
nodes = new List<Node>();
|
this.edges = new List<Edge>();
|
InitEdge(edges);
|
}
|
|
public void InitEdge(List<Tuple<ZTPoint, ZTPoint, double>> edges)
|
{
|
this.edges = ConvertToEdge(edges);
|
InitNodes();
|
}
|
|
public List<ZTPoint> Find(ZTPoint start, ZTPoint end)
|
{
|
var startNode = GetNodeByName(start);
|
var endNode = GetNodeByName(end);
|
|
if (startNode == null || endNode == null)
|
{
|
return new List<ZTPoint>();
|
}
|
|
var s = nodes.Where(x => x.Name == start).ToList();
|
var u = nodes.Where(x => x.Name != start).ToList();
|
|
s.ForEach(x =>
|
{
|
x.Weight = 0;
|
});
|
|
u.ForEach(x =>
|
{
|
x.Weight = double.PositiveInfinity;
|
});
|
|
while (u.Any())
|
{
|
var node = s.Last();
|
|
//更新node到x的距离
|
u.ForEach(x =>
|
{
|
var edge = GetEdgeByTwoNode(node, x);
|
|
if (edge != null)
|
{
|
var weights = node.GetAllWeight() + edge.Weight;
|
|
if (weights < x.Weight)
|
{
|
x.Weight = weights;
|
x.Parent = node;
|
}
|
}
|
});
|
|
//找出距离最小的
|
var minNode = u.OrderBy(x => x.Weight).FirstOrDefault();
|
|
s.Add(minNode);
|
u.Remove(minNode);
|
}
|
|
var paths = new Stack<ZTPoint>();
|
|
while (endNode != null)
|
{
|
paths.Push(endNode.Name);
|
endNode = endNode.Parent;
|
}
|
|
//如果路劲中包含起点
|
if (paths.ToList().Contains(start))
|
{
|
return paths.ToList();
|
}
|
else
|
{
|
return new List<ZTPoint>();
|
}
|
}
|
|
private Edge GetEdgeByTwoNode(Node start, Node end)
|
{
|
var edge = edges.FirstOrDefault(x => x.Start == start.Name && x.End == end.Name);
|
|
if (edge == null)
|
{
|
edge = edges.FirstOrDefault(x => x.Start == end.Name && x.End == start.Name);
|
}
|
|
return edge;
|
}
|
|
/// <summary>
|
/// 将权值转换成边
|
/// </summary>
|
/// <returns></returns>
|
private List<Edge> ConvertToEdge(List<Tuple<ZTPoint, ZTPoint, double>> weights)
|
{
|
var edges = new List<Edge>();
|
|
weights.ForEach(weight =>
|
{
|
edges.Add(new Edge()
|
{
|
Start = weight.Item1,
|
End = weight.Item2,
|
Weight = weight.Item3
|
});
|
});
|
|
return edges;
|
}
|
|
|
/// <summary>
|
/// 根据名字获取节点
|
/// </summary>
|
/// <param name="nodeName"></param>
|
/// <returns></returns>
|
private Node GetNodeByName(ZTPoint nodeName)
|
{
|
return nodes.FirstOrDefault(x => x.Name == nodeName);
|
}
|
|
/// <summary>
|
/// 初始化点
|
/// </summary>
|
private void InitNodes()
|
{
|
edges.ForEach(edge =>
|
{
|
if (nodes.All(x => x.Name != edge.Start))
|
{
|
nodes.Add(new Node()
|
{
|
Name = edge.Start
|
});
|
}
|
|
if (nodes.All(x => x.Name != edge.End))
|
{
|
nodes.Add(new Node()
|
{
|
Name = edge.End
|
});
|
}
|
});
|
}
|
}
|
}
|
