dijistra是一种贪心算法 用来求无向图两点间的最短距离
具体的内容我不多说了..
这边写的代码没有经过太多的验证 用了一个简单的例子做 所以也许还会有些地方有些问题
用的例子是
blog.csdn.net/v_july_v/article/details/6096981
内的
图和具体步骤如下:
具体代码如下:
%% @author cc fairjm %% @doc @todo Add description to dijstra_run. -module(dijstra_run). %% ==================================================================== %% API functions %% ==================================================================== -export([run/0]). run() -> %%定义距离的格式 这边的定义为 List中放入Tuple的结构(这样可以方便后面用lists库内的key系列函数) %%Tuple的结构定义为 {节点,[{与节点相连的其他节点,距离}....]} Distance=[{a,[{b,6},{c,3}]}, {b,[{a,6},{c,2},{d,5}]}, {c,[{a,3},{b,2},{d,3},{e,4}]}, {d,[{e,2},{b,5},{c,3},{f,3}]}, {e,[{c,4},{d,2},{f,5}]}, {f,[{d,3},{e,5}]} ], %%初始状态 Init=[b,c,d,e,f], %%终状态 Final=[a], %%路线初始化 结构依旧为List中放入Tuple Tuple的含义为{目标节点,目标节点和A的距离,路线} Route=[{a,0,[a]},{b,infinity,[a]},{c,infinity,[a]},{d,infinity,[a]},{e,infinity,[a]},{f,infinity,[a]}], calcu(Init,Final,Route,Distance) . %% ==================================================================== %% Internal functions %% ==================================================================== calcu([],_Final,Route,_Distance)-> Route ; calcu(Init,Final,Route,Distance) -> MinLists=lists:foldl(fun(Elem,In)-> %%当前元素到初始节点A的距离 {Elem,Elem_to_A,Elem_to_A_List}=lists:keyfind(Elem, 1,Route), %%遍历当前元素和各个节点的距离 {Elem,List}=lists:keyfind(Elem, 1, Distance), %%过滤如果目标节点比在当前表里的还大那就没必要继续算下去了 Shorter_List=lists:filter(fun({Elem2,Dis})-> %%目标节点的真实距离=当前元素到初始节点A的距离+当前元素到A的距离 Dis_to_A=Dis+Elem_to_A, {Elem2,Elem2_to_A,_}=lists:keyfind(Elem2, 1,Route), Elem2_to_A > Dis_to_A end , List), In++lists:map(fun({Elem2,Dis}) -> {Elem2,Dis+Elem_to_A,Elem_to_A_List++[Elem2]} end, Shorter_List) end, [], Final), Tuple=lists:nth(1, lists:keysort(2,MinLists)), %%拿出End用来后面更新Route的内容 {End,_,_}=Tuple, NewRoute=lists:keyreplace(End, 1, Route, Tuple), NewFinal=Final++[End], NewInit=Init--[End], io:format("~p~n", [NewRoute]), calcu(NewInit,NewFinal,NewRoute,Distance) .
代码运行如下:
28> c("dijstra_run").
{ok,dijstra_run}
29> dijstra_run:run().
[{a,0,[a]},
{b,infinity,[a]},
{c,3,[a,c]},
{d,infinity,[a]},
{e,infinity,[a]},
{f,infinity,[a]}]
[{a,0,[a]},
{b,5,[a,c,b]},
{c,3,[a,c]},
{d,infinity,[a]},
{e,infinity,[a]},
{f,infinity,[a]}]
[{a,0,[a]},
{b,5,[a,c,b]},
{c,3,[a,c]},
{d,6,[a,c,d]},
{e,infinity,[a]},
{f,infinity,[a]}]
[{a,0,[a]},
{b,5,[a,c,b]},
{c,3,[a,c]},
{d,6,[a,c,d]},
{e,7,[a,c,e]},
{f,infinity,[a]}]
[{a,0,[a]},
{b,5,[a,c,b]},
{c,3,[a,c]},
{d,6,[a,c,d]},
{e,7,[a,c,e]},
{f,9,[a,c,d,f]}]
[{a,0,[a]},
{b,5,[a,c,b]},
{c,3,[a,c]},
{d,6,[a,c,d]},
{e,7,[a,c,e]},
{f,9,[a,c,d,f]}]
{ok,dijstra_run}
29> dijstra_run:run().
[{a,0,[a]},
{b,infinity,[a]},
{c,3,[a,c]},
{d,infinity,[a]},
{e,infinity,[a]},
{f,infinity,[a]}]
[{a,0,[a]},
{b,5,[a,c,b]},
{c,3,[a,c]},
{d,infinity,[a]},
{e,infinity,[a]},
{f,infinity,[a]}]
[{a,0,[a]},
{b,5,[a,c,b]},
{c,3,[a,c]},
{d,6,[a,c,d]},
{e,infinity,[a]},
{f,infinity,[a]}]
[{a,0,[a]},
{b,5,[a,c,b]},
{c,3,[a,c]},
{d,6,[a,c,d]},
{e,7,[a,c,e]},
{f,infinity,[a]}]
[{a,0,[a]},
{b,5,[a,c,b]},
{c,3,[a,c]},
{d,6,[a,c,d]},
{e,7,[a,c,e]},
{f,9,[a,c,d,f]}]
[{a,0,[a]},
{b,5,[a,c,b]},
{c,3,[a,c]},
{d,6,[a,c,d]},
{e,7,[a,c,e]},
{f,9,[a,c,d,f]}]
相关推荐
文件中提到Dijkstra算法不能应用于有负权的图是正确的,因为算法假定所有边的权重都是非负的。 8. Floyd算法:该算法用于寻找给定加权图中所有顶点对之间的最短路径。文件中提到若不允许通过转接,使用Floyd算法求...
tornado-6.4.1-cp38-abi3-musllinux_1_2_i686.whl
tornado-6.1-cp36-cp36m-manylinux2014_aarch64.whl
基于java的ssm停车位短租系统程序答辩PPT.pptx
tornado-6.4b1-cp38-abi3-musllinux_1_1_x86_64.whl
基于java的招生管理系统答辩PPT.pptx
本压缩包资源说明,你现在往下拉可以看到压缩包内容目录 我是批量上传的基于SpringBoot+Vue的项目,所以描述都一样;有源码有数据库脚本,系统都是测试过可运行的,看文件名即可区分项目~ |Java|SpringBoot|Vue|前后端分离| 开发语言:Java 框架:SpringBoot,Vue JDK版本:JDK1.8 数据库:MySQL 5.7+(推荐5.7,8.0也可以) 数据库工具:Navicat 开发软件: idea/eclipse(推荐idea) Maven包:Maven3.3.9+ 系统环境:Windows/Mac
基于java的农机电招平台答辩PPT.pptx
jdk23 甲骨文官方安装包
基于java的机场网上订票系统答辩PPT.pptx
项目经过测试均可完美运行! 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse
基于java的网上书店销售管理系统答辩PPT.pptx
tornado-6.3.3-cp38-abi3-win32.whl
【作品名称】:基于 Jsp+Sqlserver 实现的超市信息管理系统 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【项目介绍】: 系统功能: (1)系统分两种身份:管理员和员工,选择不同的身份进入不同的功能操作界面! (2)商品信息管理:管理员可以添加和维护商品信息,员工只能对商品信息进行查询 (3)员工信息管理:管理员登陆系统后可以可以添加和维护超市员工(收银员)的信息 (4)商品进货管理:管理员登陆系统后可以添加商品进货信息,可以对商品进货信息进行查询和统计,添加商品进进货退货信息,对商品进货退货信息进行查询和统计 (5)商品销售管理:员工(收银员)登陆系统后可以对商品进行销售,可以按时间查询自己的销售业绩;管理员登陆系统后可以按照时间等条件对销售信息进行查询,可以根据小票号登记顾客退货信息,查询顾客退货信息,可以查看员 【资源声明】:本资源作为“参考资料”而不是“定制需求”,代码只能作为参考,不能完全复制照搬。需要有一定的基础看懂代码,自行调试代码并解决报错,能自行添加功能修改代码。
tornado-6.3.2-cp38-abi3-musllinux_1_1_i686.whl
基于java的热带水果商城答辩PPT.pptx
java awt、Swing实现中国象棋可联机版本采用面向对象思想 采用面向对象的思路,实现中国象棋可联机版本,适合初学者,以及对面向对象有更深层次理解的开发者或者同学。 使用原生的java awt、Swing进行窗口式开发 将素材文件夹放在D:\Game路径下 两个工程直接导入Eclipse,即可运行, ps:一个工程运行两次也可以,需要注意端口号,代码默认如果连接的端口号是3003,则监听3004端口,相反同理。联机前需要确保两台计算机同时处于局域网或外网
web前端设计与开发(详细整理)(包含html讲解,css讲解,移动web讲解),合适学习前端的人员进行基础学习,一秒变高手
分析所需的数据和代码都在这里
Listening Exercise 3 Part 2.mp3