47 lines
1.7 KiB
Erlang
47 lines
1.7 KiB
Erlang
-module(dijkstra).
|
|
-include_lib("eunit/include/eunit.hrl").
|
|
-export([dijkstrafy/3]).
|
|
|
|
% just hide away recursion so we have a nice interface
|
|
dijkstrafy(Graph, Start, End) when is_map(Graph) ->
|
|
shortest_path(Graph, [{0, [Start]}], End, #{}).
|
|
|
|
shortest_path(_Graph, [], _End, _Visited) ->
|
|
% if we're not going anywhere, it's time to start going back
|
|
{0, []};
|
|
shortest_path(_Graph, [{Cost, [End | _] = Path} | _ ], End, _Visited) ->
|
|
% this is the base case, and finally returns the distance and the path
|
|
{Cost, lists:reverse(Path)};
|
|
shortest_path(Graph, [{Cost, [Node | _ ] = Path} | Routes], End, Visited) ->
|
|
% this is the recursive case.
|
|
% here we build a list of new "unvisited" routes, where the stucture is
|
|
% a tuple of cost, then a list of paths taken to get to that cost from the "Start"
|
|
NewRoutes = [{Cost + NewCost, [NewNode | Path]}
|
|
|| {NewCost, NewNode} <- maps:get(Node, Graph),
|
|
not maps:get(NewNode, Visited, false)],
|
|
shortest_path(
|
|
Graph,
|
|
% add the routes we ripped off earlier onto the new routes
|
|
% that we want to visit. sort the list of routes to get the
|
|
% shortest routes (lowest cost) at the beginning.
|
|
% Erlangs sort is already good enough, and it will sort the
|
|
% tuples by the number at the beginning of each (the cost).
|
|
lists:sort(NewRoutes ++ Routes),
|
|
End,
|
|
Visited#{Node => true}
|
|
).
|
|
|
|
basic_test() ->
|
|
Graph = #{
|
|
a => [{7,b},{9,c},{14,f}],
|
|
b => [{7,a},{10,c},{15,d}],
|
|
c => [{10,b},{9,c},{11,d},{2,f}],
|
|
d => [{15,b},{6,e},{11,c}],
|
|
e => [{9,f},{6,d}],
|
|
f => [{14,f},{2,c},{9,e}]
|
|
},
|
|
{Cost, Path} = dijkstrafy(Graph, a, e),
|
|
{20,[a,c,f,e]} = {Cost, Path},
|
|
io:format(user, "The total cost was ~p and the path was: ", [Cost]),
|
|
io:format(user, "~w~n", [Path]).
|