[习题]erlang算法练习-dijstra

[练习]erlang算法练习--dijstra

?

?

具体代码如下:

%% @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_Aend, 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]}]

?

查看更多 下一篇