网站空间怎样设置用户名和密码,苏州建设公司网站建设,学生作业 制作一个网站,wordpress 做api接口最短路径查找算法
寻路算法在生活中应用十分常见。本文实现的是关于图的最短路径查找算法。 该算法比较常见于游戏和室内地图导航。
实现
例子#xff1a;几个节点之间#xff0c;相连接的线段有固定长度#xff0c;该长度决就是通过代价。查找到花费最少的路径。该图结构…最短路径查找算法
寻路算法在生活中应用十分常见。本文实现的是关于图的最短路径查找算法。 该算法比较常见于游戏和室内地图导航。
实现
例子几个节点之间相连接的线段有固定长度该长度决就是通过代价。查找到花费最少的路径。该图结构为 #mermaid-svg-M7b9IFyeerNhHXuI {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-M7b9IFyeerNhHXuI .error-icon{fill:#552222;}#mermaid-svg-M7b9IFyeerNhHXuI .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-M7b9IFyeerNhHXuI .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-M7b9IFyeerNhHXuI .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-M7b9IFyeerNhHXuI .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-M7b9IFyeerNhHXuI .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-M7b9IFyeerNhHXuI .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-M7b9IFyeerNhHXuI .marker{fill:#333333;stroke:#333333;}#mermaid-svg-M7b9IFyeerNhHXuI .marker.cross{stroke:#333333;}#mermaid-svg-M7b9IFyeerNhHXuI svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-M7b9IFyeerNhHXuI .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-M7b9IFyeerNhHXuI .cluster-label text{fill:#333;}#mermaid-svg-M7b9IFyeerNhHXuI .cluster-label span{color:#333;}#mermaid-svg-M7b9IFyeerNhHXuI .label text,#mermaid-svg-M7b9IFyeerNhHXuI span{fill:#333;color:#333;}#mermaid-svg-M7b9IFyeerNhHXuI .node rect,#mermaid-svg-M7b9IFyeerNhHXuI .node circle,#mermaid-svg-M7b9IFyeerNhHXuI .node ellipse,#mermaid-svg-M7b9IFyeerNhHXuI .node polygon,#mermaid-svg-M7b9IFyeerNhHXuI .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-M7b9IFyeerNhHXuI .node .label{text-align:center;}#mermaid-svg-M7b9IFyeerNhHXuI .node.clickable{cursor:pointer;}#mermaid-svg-M7b9IFyeerNhHXuI .arrowheadPath{fill:#333333;}#mermaid-svg-M7b9IFyeerNhHXuI .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-M7b9IFyeerNhHXuI .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-M7b9IFyeerNhHXuI .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-M7b9IFyeerNhHXuI .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-M7b9IFyeerNhHXuI .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-M7b9IFyeerNhHXuI .cluster text{fill:#333;}#mermaid-svg-M7b9IFyeerNhHXuI .cluster span{color:#333;}#mermaid-svg-M7b9IFyeerNhHXuI div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-M7b9IFyeerNhHXuI :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 5米 2米 4米 5米 2米 2米 2米 8米 起点A B C F 终点D 思路
可以看到 ABD与ACD 的代价都相同边相加都等于10. 而ACB的路线代价扽与9是最短路径。
将每个节点的子节点包括路径都保存成散列表。递归检查每个相关节点看是否能到达终点并记录下代价、路线、并保存好与上次成功到达终点的路径相比代价较小的路径。不断更新直到循环每个节点。最后输出的结果就是想要的最短路径
复杂度最坏情况应该就是O((n-1)2) 了吧
不参考加权求任意两点间的所有路径
//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 Liststring rotearray new Liststring();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
当前结构:AC
当前节点D
当前结构:ACD
到达终点路径:ACD当前节点B
当前结构:ACB
当前节点F
当前结构:ACBF
当前节点D
当前结构:ACBD
到达终点路径:ACBD当前节点F
当前结构:AF
当前节点B
当前结构:AB
当前节点F
当前结构:ABF
当前节点D
当前结构:ABD
到达终点路径:ABD求指定两点间代价最小(最短)路径
此段代码用于求出加权图最短路径加入了防循环可以在有向图、无向图中使用
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 Liststring pathList new Liststring();static Listint pathCostList new Listint();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 i0; 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
当前结构:AC
当前节点D
当前结构:ACD
到达终点路径:ACD
代价:10米
害羞而淫荡的分割线
当前节点B
当前结构:ACB
当前节点F
当前结构:ACBF
当前节点D
当前结构:ACBD
到达终点路径:ACBD
代价:9米
害羞而淫荡的分割线
当前节点F
当前结构:AF
当前节点B
当前结构:AFB
当前节点D
当前结构:AFBD
到达终点路径:AFBD
代价:9米
害羞而淫荡的分割线
当前节点B
当前结构:AB
当前节点F
当前结构:ABF
当前节点D
当前结构:ABD
到达终点路径:ABD
代价:10米
害羞而淫荡的分割线
最短路径ACBD 代价:9米
有权图理论上来说把权化为等量节点也可以使用最短节点算法求最短路径。
