55 lines
2.0 KiB
Erlang
55 lines
2.0 KiB
Erlang
-module(floyd_warshall).
|
|
-export([main/2]).
|
|
|
|
|
|
main(N, Edge) ->
|
|
{Dist, Next} = setup(N, Edge),
|
|
{Dist2, Next2} = shortest_path(N, Dist, Next),
|
|
print(N, Dist2, Next2).
|
|
|
|
setup(N, Edge) ->
|
|
Big = 1.0e300,
|
|
Dist = maps:from_list([{{I,J}, case I == J of true -> 0; false -> Big end}
|
|
|| I <- lists:seq(1, N), J <- lists:seq(1, N)]),
|
|
Next = maps:from_list([{{I,J}, nil}
|
|
|| I <- lists:seq(1, N), J <- lists:seq(1, N)]),
|
|
lists:foldl(fun({U, V, W}, {Dst, Nxt}) ->
|
|
{maps:put({U, V}, W, Dst), maps:put({U, V}, V, Nxt)}
|
|
end, {Dist, Next}, Edge).
|
|
|
|
shortest_path(N, Dist, Next) ->
|
|
Combinations = [{K, I, J} || K <- lists:seq(1, N),
|
|
I <- lists:seq(1, N),
|
|
J <- lists:seq(1, N)],
|
|
lists:foldl(fun({K, I, J}, {Dst, Nxt}) ->
|
|
IJ_Dist = maps:get({I, J}, Dst),
|
|
IK_Dist = maps:get({I, K}, Dst),
|
|
KJ_Dist = maps:get({K, J}, Dst),
|
|
case IJ_Dist > IK_Dist + KJ_Dist of
|
|
true ->
|
|
NewDist = maps:put({I, J}, IK_Dist + KJ_Dist, Dst),
|
|
NewNext = maps:put({I, J}, maps:get({I, K}, Nxt), Nxt),
|
|
{NewDist, NewNext};
|
|
false ->
|
|
{Dst, Nxt}
|
|
end
|
|
end, {Dist, Next}, Combinations).
|
|
|
|
print(N, Dist, Next) ->
|
|
io:format("pair dist path~n"),
|
|
[io:format("~w -> ~w ~4w ~s~n", [I, J, maps:get({I, J}, Dist), path(Next, I, J)])
|
|
|| I <- lists:seq(1, N), J <- lists:seq(1, N), I =/= J].
|
|
|
|
path(Next, I, J) ->
|
|
PathList = path(Next, I, J, [I]),
|
|
string:join([integer_to_list(X) || X <- PathList], " -> ").
|
|
|
|
path(_Next, I, I, List) ->
|
|
lists:reverse(List);
|
|
path(Next, I, J, List) ->
|
|
U = maps:get({I, J}, Next),
|
|
path(Next, U, J, [U | List]).
|
|
|
|
% Usage example:
|
|
main(_) -> main(4, [{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}]).
|