前言:此算法是解决从原点出发到其他节点的最短路径。但是也有此算法的限制条件和前提
- 路径是有方向且无环的
- 路径的消耗不为负数(权重不为负数)
题目:如下图所示,从起点为A,终点为F,路径每一条边上的数字为消耗的时间权重,求A点到F点最少需要多少时间?
狄克斯特拉算法按照如下规则运行
- 找出目前知道的最便宜的节点,即最短时间内到达的节点(不知道的节点算无穷大,如:D、E、F)。
- 更新对应最便宜节点相邻节点的开销。
- 对图中的每个节点都执行第一步和第二步,直到没有节点可执行为止。
- 计算最终节点
示例代码如下:
using System.Collections.Generic;
using UnityEngine;
public class DijkstraAlgorithm : MonoBehaviour
{
///
/// 相当于Main函数
///
void Start()
{
InvokeDijkstra();
}
///
/// 对应的节点到周围节点需要的时间(权重)
///
private Dictionary> graphDictionary = new Dictionary>();
///
/// 从原点到指定节点需要的时间(权重)
///
private Dictionary sourceToNodeCost = new Dictionary();
///
/// 节点对应的父节点
///
private Dictionary nodeParentDictionary = new Dictionary();
///
/// 已经处理过的节点集合,此处理更新对应最便宜节点相邻节点的开销
///
private List processedNodeList = new List();
public void InvokeDijkstra()
{
//初始化节点和对应邻居节点的数据结构
graphDictionary.Add("A", new Dictionary());
graphDictionary.Add("B", new Dictionary());
graphDictionary.Add("C", new Dictionary());
graphDictionary.Add("D", new Dictionary());
graphDictionary.Add("E", new Dictionary());
graphDictionary.Add("F", new Dictionary());
//添加对应的节点到邻居节点的花销
graphDictionary["A"].Add("B", 4.0f);
graphDictionary["A"].Add("C", 1.0f);
graphDictionary["B"].Add("D", 12.0f);
graphDictionary["B"].Add("E", 15.0f);
graphDictionary["C"].Add("D", 23.0f);
graphDictionary["C"].Add("E", 429.0f);
graphDictionary["D"].Add("F", 19.0f);
graphDictionary["E"].Add("F", 9.0f);
//原点是第一个节点,所以花费为0
sourceToNodeCost.Add("A", 0);
var lowestConstNodeName = FindLowestConstNode(sourceToNodeCost);
while (!string.IsNullOrEmpty(lowestConstNodeName))
{
//找到对应的邻居
foreach (var node in graphDictionary[lowestConstNodeName])
{
//节点的总体花费 = 原点到父节点的总体花费 + 父节点到此节点的花费
float tempCost = sourceToNodeCost[lowestConstNodeName] + node.Value;
float originalCost = sourceToNodeCost.ContainsKey(node.Key) ? sourceToNodeCost[node.Key] : float.PositiveInfinity;
if (tempCost< originalCost)
{
sourceToNodeCost[node.Key] = tempCost;
nodeParentDictionary[node.Key] = lowestConstNodeName;
}
}
//此节点已经完成处理
processedNodeList.Add(lowestConstNodeName);
//查找下一个花费最少并且没有处理的节点
lowestConstNodeName = FindLowestConstNode(sourceToNodeCost);
}
var fullPath = ShortestPath("F");
Debug.Log($"最短的路径为:{fullPath}");
}
///
/// 发现时间最少且没有被处理的节点
///
///
public string FindLowestConstNode(Dictionary sourceToNodeCost)
{
float tempValue = float.PositiveInfinity;
string nodeName = "";
foreach (var node in sourceToNodeCost)
{
if (!processedNodeList.Contains(node.Key))
{
if (node.Value < tempValue)
{
tempValue = node.Value;
nodeName = node.Key;
}
}
}
return nodeName;
}
///
/// 找到最短路径的节点路线
///
///
///
public string ShortestPath(string finalNodeName)
{
string result = "";
if (nodeParentDictionary.ContainsKey(finalNodeName))
{
result += ShortestPath(nodeParentDictionary[finalNodeName]);
result += finalNodeName + " --> ";
}
else
{
result += finalNodeName + " --> ";
}
return result;
}
}
阅读量: 1,854