using System;
|
using System.Collections.Generic;
|
using System.Linq;
|
using System.Text;
|
using System.Threading.Tasks;
|
|
namespace RichCreator.Utility.PathFinding
|
{
|
public class Dijkstra<T> where T : IEquatable<T>
|
{
|
private Dictionary<T, Dictionary<T, Int32>> edges = new Dictionary<T, Dictionary<T, Int32>>();
|
|
/// <summary>
|
/// 添加顶点
|
/// </summary>
|
/// <param name="vertice">顶点名称</param>
|
/// <param name="targetVertice">顶点所有的边</param>
|
public void AddEdge(T vertice, Dictionary<T, Int32> targetVertice)
|
{
|
foreach (var item in targetVertice)
|
{
|
AddEdge(vertice, item.Key, item.Value);
|
}
|
}
|
|
/// <summary>
|
/// 添加顶点
|
/// </summary>
|
/// <param name="vertice">顶点名称</param>
|
/// <param name="targetVertice">可连接顶点</param>
|
/// <param name="weight">权重</param>
|
public void AddEdge(T vertice, T targetVertice, Int32 weight)
|
{
|
if (!this.edges.ContainsKey(vertice))
|
{
|
this.edges.Add(vertice, new Dictionary<T, Int32>());
|
}
|
|
if (!this.edges[vertice].ContainsKey(targetVertice))
|
{
|
this.edges[vertice].Add(targetVertice, weight);
|
}
|
|
|
if (!this.edges.ContainsKey(targetVertice))
|
{
|
this.edges.Add(targetVertice, new Dictionary<T, Int32>());
|
}
|
|
|
if (!this.edges[targetVertice].ContainsKey(vertice))
|
{
|
this.edges[targetVertice].Add(vertice, weight);
|
}
|
|
}
|
|
/// <summary>
|
/// 移除顶点
|
/// </summary>
|
/// <param name="name"></param>
|
public void RemoveEdge(T name)
|
{
|
if (this.edges.ContainsKey(name))
|
{
|
return;
|
}
|
this.edges.Remove(name);
|
foreach (var item in this.edges)
|
{
|
if (item.Value.ContainsKey(name))
|
{
|
item.Value.Remove(name);
|
}
|
}
|
}
|
|
/// <summary>
|
/// 查找最短路径
|
/// </summary>
|
/// <param name="start"></param>
|
/// <param name="finish"></param>
|
/// <returns></returns>
|
|
public List<T> ShortestPath(T start, T finish)
|
{
|
var previous = new Dictionary<T, T>();
|
var distances = new Dictionary<T, Int32>();
|
var nodes = new List<T>();
|
|
List<T> path = new List<T>();
|
|
foreach (var vertex in edges)
|
{
|
if (vertex.Key.Equals(start))
|
{
|
distances[vertex.Key] = 0;
|
}
|
else
|
{
|
distances[vertex.Key] = Int32.MaxValue;
|
}
|
|
nodes.Add(vertex.Key);
|
}
|
|
while (nodes.Count != 0)
|
{
|
nodes.Sort((x, y) => distances[x] - distances[y]);
|
|
var smallest = nodes[0];
|
nodes.Remove(smallest);
|
|
if (smallest.Equals(finish))
|
{
|
while (previous.ContainsKey(smallest))
|
{
|
path.Add(smallest);
|
smallest = previous[smallest];
|
}
|
|
//倒译排列
|
path.Reverse();
|
|
break;
|
}
|
|
if (distances[smallest] == Int32.MaxValue)
|
{
|
break;
|
}
|
|
foreach (var neighbor in edges[smallest])
|
{
|
var alt = distances[smallest] + neighbor.Value;
|
if (alt < distances[neighbor.Key])
|
{
|
distances[neighbor.Key] = alt;
|
previous[neighbor.Key] = smallest;
|
}
|
}
|
}
|
|
return path;
|
}
|
}
|
}
|
