网站建设分期收费北京竞价托管代运营

最短路径查找算法

寻路算法在生活中应用十分常见。本文实现的是关于图的最短路径查找算法。
该算法比较常见于游戏和室内地图导航。

实现

例子：几个节点之间，相连接的线段有固定长度，该长度决就是通过代价。查找到花费最少的路径。该图结构为

思路：

可以看到 A>B>D与A>C>D 的代价都相同，边相加都等于10. 而A>C>B的路线代价扽与9，是最短路径。

1. 将每个节点的子节点包括路径都保存成散列表。
2. 递归检查每个相关节点，看是否能到达终点，并记录下代价、路线、并保存好与上次成功到达终点的路径相比，代价较小的路径。
3. 不断更新直到循环每个节点。
4. 最后输出的结果就是想要的最短路径

复杂度：最坏情况应该就是O((n-1)²) 了吧

不参考加权，求任意两点间的所有路径

//csharp版代码using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;namespace ConsoleApp1test
{class Program{   //创建图数据static Hashtable myGraph = new Hashtable();static void Main(string[] args) {//A节点及其信息与关系myGraph["A"] = new Hashtable();(myGraph["A"] as Hashtable)["B"] = 5;(myGraph["A"] as Hashtable)["C"] = 2;(myGraph["A"] as Hashtable)["F"] = 2;//B节点myGraph["B"] = new Hashtable();(myGraph["B"] as Hashtable)["D"] = 5;(myGraph["B"] as Hashtable)["F"] = 5;//CmyGraph["C"] = new Hashtable();(myGraph["C"] as Hashtable)["B"] = 2;(myGraph["C"] as Hashtable)["D"] = 8;//DmyGraph["D"] = new Hashtable();//fmyGraph["F"] = new Hashtable();//递归监测GetPath(myGraph["A"] as Hashtable, "A", "D");Console.ReadKey();}//创建用于存储代价的变量static int cost = 0;//创建用于记录路径的数据表static Hashtable rote = new Hashtable();static List<string> rotearray = new List<string>();public static void GetPath(Hashtable targetNode, string startPoint, string endPoint){//记录当前节点rotearray.Add(startPoint);Console.WriteLine("当前节点："+ startPoint);string st = "";foreach (string name in rotearray){st += name + ">";}Console.WriteLine("当前结构:"+st);//当前节点是否是根节点if (startPoint == endPoint){//已经到达终点  //输出当前分支的每个节点string s = "";foreach (string name in rotearray){s += name + ">";}Console.WriteLine("到达终点，路径:"+s);Console.WriteLine("=================");} else {//未到达指定节点 遍历每个节点下相关联的子节点foreach (string connected_node_name in targetNode.Keys)//在第一次输入时，不应该遍历所有的值{GetPath(myGraph[connected_node_name] as Hashtable, connected_node_name, endPoint);}}//删除当前节点回 到上层if (rotearray.Count > 0)rotearray.RemoveAt(rotearray.Count - 1);}}
}

结果：

当前节点：A
当前结构:A>
当前节点：C
当前结构:A>C>
当前节点：D
当前结构:A>C>D>
到达终点，路径:A>C>D>
=================
当前节点：B
当前结构:A>C>B>
当前节点：F
当前结构:A>C>B>F>
当前节点：D
当前结构:A>C>B>D>
到达终点，路径:A>C>B>D>
=================
当前节点：F
当前结构:A>F>
当前节点：B
当前结构:A>B>
当前节点：F
当前结构:A>B>F>
当前节点：D
当前结构:A>B>D>
到达终点，路径:A>B>D>
=================

求指定两点间代价最小(最短)路径

此段代码，用于求出加权图最短路径，加入了防循环，可以在有向图、无向图中使用

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;namespace ConsoleApp1test
{class Program{   //创建图数据static Hashtable myGraph = new Hashtable();static void Main(string[] args) {//A节点及其信息与关系myGraph["A"] = new Hashtable();(myGraph["A"] as Hashtable)["B"] = 5;(myGraph["A"] as Hashtable)["C"] = 2;(myGraph["A"] as Hashtable)["F"] = 2;//B节点myGraph["B"] = new Hashtable();(myGraph["B"] as Hashtable)["D"] = 5;(myGraph["B"] as Hashtable)["F"] = 5;//CmyGraph["C"] = new Hashtable();(myGraph["C"] as Hashtable)["B"] = 2;(myGraph["C"] as Hashtable)["D"] = 8;//DmyGraph["D"] = new Hashtable();//fmyGraph["F"] = new Hashtable();(myGraph["F"] as Hashtable)["B"] = 2;//递归监测GetPath(myGraph["A"] as Hashtable, "A", "D");Console.WriteLine("最短路径：" + shortestPath + " 代价:" + shortestCost + "米");Console.ReadKey();}//创建用于存储代价\记录路径的数据表static List<string> pathList = new List<string>();static List<int> pathCostList = new List<int>();static int shortestCost = 100000;static string shortestPath = "";public static void GetPath(Hashtable targetNode, string startPoint, string endPoint){//记录当前节点pathList.Add(startPoint);Console.WriteLine("当前节点："+ startPoint);string allPath = "";for(int i=0; i < pathList.Count; i++){allPath += pathList[i];allPath += (i == (pathList.Count - 1)) ? "" : ">";}Console.WriteLine("当前结构:" + allPath);//当前节点是否是根节点if (startPoint == endPoint){//已经到达终点  //输出当前分支的每个节点Console.WriteLine("到达终点,路径:"+ allPath);//计算所有的权值int pathCost_total = 0;foreach (int pathCost in pathCostList){pathCost_total += pathCost;}Console.WriteLine("代价:" + pathCost_total.ToString() + "米");//更新最短路径信息if (pathCost_total < shortestCost) {shortestCost = pathCost_total;shortestPath = allPath;}Console.WriteLine("==========害羞而淫荡的分割线==========");} else {//未到达指定节点 遍历每个节点下相关联的子节点foreach (string connected_node_name in targetNode.Keys){//如果，路径中已存在节点，就不走了。 避免循环。if (!pathList.Contains(connected_node_name)) {//记录路径权值pathCostList.Add((int)targetNode[connected_node_name]);GetPath(myGraph[connected_node_name] as Hashtable, connected_node_name, endPoint);//记录路径权值if (pathCostList.Count > 0)pathCostList.RemoveAt(pathCostList.Count - 1);}}}//删除当前节点回 到上层if (pathList.Count > 0)pathList.RemoveAt(pathList.Count - 1);}}
}

结果:

当前节点：A
当前结构:A
当前节点：C
当前结构:A>C
当前节点：D
当前结构:A>C>D
到达终点，路径:A>C>D
代价:10米
==========害羞而淫荡的分割线==========
当前节点：B
当前结构:A>C>B
当前节点：F
当前结构:A>C>B>F
当前节点：D
当前结构:A>C>B>D
到达终点，路径:A>C>B>D
代价:9米
==========害羞而淫荡的分割线==========
当前节点：F
当前结构:A>F
当前节点：B
当前结构:A>F>B
当前节点：D
当前结构:A>F>B>D
到达终点，路径:A>F>B>D
代价:9米
==========害羞而淫荡的分割线==========
当前节点：B
当前结构:A>B
当前节点：F
当前结构:A>B>F
当前节点：D
当前结构:A>B>D
到达终点，路径:A>B>D
代价:10米
==========害羞而淫荡的分割线==========
最短路径：A>C>B>D 代价:9米

有权图，理论上来说把权化为等量节点，也可以使用最短节点算法求最短路径。