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]}]
相关推荐
- 使用yum安装Erlang:`sudo yum install erlang-23.3.4.3-1.el7.x86_64.rpm` 2. **安装RabbitMQ**: - 下载RabbitMQ RPM包:`wget https://your_download_link/rabbitmq-server-3.8.17-1.el7.noarch.rpm` - ...
erlang-20.3.8.17-1.el7.centos.x86_64
erlang-xmerl-22.3-1.el7.x86_64.rpm,rabbitMQ安装需要依赖此环境。Erlang 是一种多用途编程语言,主要用于开发并发和分布式系统。它最初是一种专有的编程语言,Ericsson 使用它来开发电话和通信应用程序。
erlang-sd_notify-1.0-2.el7.x86_64.rpm
erlang-21.3.8.11-1.el6.x86_64.rpm
erlang-xmerl-23.0.2-2.el7.x86_64.rpm,rabbitMQ安装需要依赖此环境。Erlang 是一种多用途编程语言,主要用于开发并发和分布式系统。它最初是一种专有的编程语言,Ericsson 使用它来开发电话和通信应用程序。
erlang-19.3.6.4-1.el
https://blog.51cto.com/7794482/2436678 可根据文档进行部署,redis+mysql+mq的插件 rabbitmq 安装时需要该插件
erlang-21.3.8.15-1.el7.x86_64.rpm
erlang-20.3.6-1.el7.centos.x86_64.rpm erlang-20.3.6-1.el7.centos.x86_64.rpm erlang-20.3.6-1.el7.centos.x86_64.rpm erlang-20.3.6-1.el7.centos.x86_64.rpm erlang-20.3.6-1.el7.centos.x86_64.rpm
erlang-21.3.7.1-1.el7.x86_64.rpm rabbitmq基础语言环境。
对应rabbitmq 3.12.4,亲测可用
linux基于centos7.x,erlang21.3.8.16资源适配rabbitmq3.8.5。欢迎大家下载!!!!
erlang-23.2.7-1.el7.x86_64 .rpm
配套rabbitmq-server-3.8.17-1.el8.noarch.rpm
erlang-23.2.6-1.el7.x86_64
erlang-erl_interface-19.3.6.4-1.el7.x86_64.rpm
rabbitmq安装前需要安装erlang包,如果没有erlang包,rabbitmp则无法下载成功
由于不同版本的rabbitmq需要的erlang版本不一样,但是官网已经无法下载,此版本的erlang适用于rabbitmq3.7.4-3.7.8,其余版本自查是否可用
esl-erlang_24.2.1-1_centos_7_amd64.rpm