-
C#-狄克斯特拉(Dijkstra)算法简单示例
Dijkstra算法用于寻找两个站点(起点到终点)之间的最短路径。本文从使用角度介绍步骤，概念理论可自行百度。
算法使用前提是站点之间的互通关系及路径长度(权重)已知，例如计算图中AE之间的最短路线：
寻路步骤为：
建立两个集合S和U，S表示已确定与A最短路线的站点集合；U表示未确定的站点集合。
初始时，S=[A],U=[B,C,D,E];
1.罗列集合U中与起点A互通的站点，分别计算其路径长度B:2,C:13;
2.将长度最小的站B添加到集合S，并从集合U删除。S=[A,B:2],U=[C:13,D,E];
3.罗列集合U中与B互通的站点，分别计算其路径长度：ABC=12<AC=13，所以C的长度更新为12，ABD:8；
4.将长度最小的站D添加到集合S，并从集合U删除，S=[A,B:2,D:8],U=[C:12,E];
5.罗列集合U中与D互通的站点，分别计算路径长度：ABDC=9<ABC=12，所以C的长度更新为9，ABDE:12;
6.将长度最小的站C添加到集合S，并从集合U删除，S=[A,B:2,D:8,C:9],U=[E:12];
7.计算ABDCE=14<ABDE=12,将E加入集合S并从U删除，S=[A,B:2,D:8,C:9,E:12],U=[];
8.得到最终结果，路径为ABDE，长度为12；
对上述计算步骤再次进行总结：
1.将起点放入集合S，其余待确定路线点放入集合U。集合U中的站的上一站均为Unknown，长度为无穷大。
2.遍历U，计算所有与集合S的末尾站n互通的站的长度，
若上一站为未知，则直接标记它们的上一站为n，记录它们的长度；
若上一站已标记，则比较本次计算长度与记录的长度，若本次更小，则更新上一站与长度记录，否则不变；
3.将这些点中已知长度最小的点放入集合S，并从集合U删除。若集合U中无已知长度的站，则寻路失败。
4.判断集合S中是否已包含了终点即起点到终点的路径已确定，若已确定，结束计算，若未确定，跳至步骤2.
代码实现：如图方框中的数字表示经过此站点的长度，设定只能上下左右移动，实现任意两站的最短路径计算。
先初始化按钮的长度和互通关系：
void InitStationLength()
{
refresh = new Dictionary<Button, Color>();
staLength = new Dictionary<string, int>();
btList = new Dictionary<string, Button>();
foreach (Control c in this.Controls)
{
if (c is Button)
{
staLength.Add(c.Name, Convert.ToInt16(c.Text));
btList.Add(c.Name, c as Button);
}
}
}
void InitLinkRoute()
{
linkList = new Dictionary<string, List<string>>();
string[] vList = { "a", "b", "c", "d", "e", "f", "g" };
for (int v = 0; v < 7; v++)
{
for (int h = 1; h < 7; h++)
{
linkList.Add("bt_" + vList[v] + h, new List<string>());
if (h != 1)
linkList["bt_" + vList[v] + h].Add("bt_" + vList[v] + (h - 1));
if (h != 6)
linkList["bt_" + vList[v] + h].Add("bt_" + vList[v] + (h + 1));
if (v != 0)
linkList["bt_" + vList[v] + h].Add("bt_" + vList[v - 1] + h);
if (v != 6)
linkList["bt_" + vList[v] + h].Add("bt_" + vList[v + 1] + h);
}
}
}
点击任意两个按钮自动开始计算路径，计算过程：
void CalculateRoute(object flag)
{
string start = buffer[0];
string end = buffer[1];
buffer.Clear();
List<Station> sList = new List<Station>();//存放已确定路径的点
List<Station> uList = new List<Station>();//待确定路径的点
sList.Add(new Station()
{
name = start,
length = 0,
preST = "",
});//将起点记入
foreach (var v in linkList)
{
if (v.Key == start)
continue;
uList.Add(new Station()
{
name = v.Key,
length = -1,
preST = "",
});
}//将除起点外其他点记入
while (true)
{
Thread.Sleep(50);
uList.ForEach(sta =>
{
if (linkList[sList.Last().name].Contains(sta.name))//罗列集合U中与Last互通的站
{
if (sta.length == -1 || (sList.Last().length + staLength[sta.name] < sta.length))//如果未标记或新的长度小于之前的长度
{
sta.preST = sList.Last().name;//标记上一站
sta.length = sList.Last().length + staLength[sta.name];//记录长度
}
}
});
Station st = null;
uList.ForEach(u =>
{
if (u.length != -1)
{
if (st == null || u.length < st.length)
st = u;//取出集合U中长度最小的站
}
});
if (st == null)
break;//若无则结束
uList.Remove(st);
sList.Add(st);//从集合U中删除添加到集合S
Add(btList[st.name], Color.Blue);
if (uList.Count == 0)
break;//若U全部删除则结束
if (sList.Last().name == end)
break;//若集合S中已包含终点，则结束
}
List<string> result = new List<string>();
result.Add(end);
while (true)
{
result.Insert(0, sList.Find(s => s.name == result[0]).preST);
if (result[0] == start)
break;
}//根据标记的上一站，依次得到起点到终点的路径。
foreach (var v in btList)
{
if (result.Contains(v.Key))
Add(v.Value, Color.DarkOrange);
}
}
测试计算效果：橙色为计算出的路径，蓝色为计算过程中加入到S集合中的站点，也代表了计算量。
算法的劣势，例如相邻两个点，距离较大时会一直寻找较短的路线，直至无法找到更短的才结束：
出处：https://www.cnblogs.com/cfsl/p/16889762.html
