Erlang 中 Dijkstra 算法使用什么数据结构？

Question

免责声明：作者是 Erlang 新手。

想象一下，我们有一个由 1M 个节点组成的图，每个节点有 0-4 个邻居（边从每个节点发散到这些邻居，所以图是有向且连通的）。

以下是我选择的数据结构：

为了存储图表，我使用有向图，它基于 ETS 表。这允许快速（O(1)）访问节点的邻居。

对于未访问节点列表，我使用gb_sets:take_smallest（节点已经排序，获取后同时删除）。

对于前驱列表，我使用 dict 结构，它允许通过以下方式存储前驱：{Node1,Node1_predecessor},{Node2,Node2_predecessor}。

对于访问节点的列表，我使用一个简单的列表。

问题：

1. 当我尝试更新有向图结构和 Unvisited_nodes 结构中节点的权重时，代码变得非常难以阅读和维护。将一个“对象”与需要在两个数据结构中同时更新的“字段”保留在一起似乎不是正确的方法。这样做的正确方法是什么？
2. 同样的问题是关于前辈名单的。我应该在哪里存储节点“对象”的前驱“字段”？也许在图中（有向图结构）？
3. 也许我应该根据进程和消息而不是对象（节点和边）及其字段（权重）重新思考整个 Dijkstra 算法？

UPD：

以下是基于 Antonakos 的建议的代码：

dijkstra(Graph,Start_node_name) ->

    io:format("dijkstra/2: start~n"),

    Paths = dict:new(),
    io:format("dijkstra/2: initialized empty Paths~n"),

    Unvisited = gb_sets:new(),
    io:format("dijkstra/2: initialized empty Unvisited nodes priority queue~n"),

    Unvisited_nodes = gb_sets:insert({0,Start_node_name,root},Unvisited),
    io:format("dijkstra/2: Added start node ~w with the weight 0 to the Unvisited nodes: ~w~n", [Start_node_name, Unvisited_nodes]),

    Paths_updated = loop_through_nodes(Graph,Paths,Unvisited_nodes),
    io:format("dijkstra/2: Finished searching for shortest paths: ~w~n", [Paths_updated]).




loop_through_nodes(Graph,Paths,Unvisited_nodes) ->
    %% We need this condition to stop looping through the Unvisited nodes if it is empty
    case gb_sets:is_empty(Unvisited_nodes) of
        false -> 
            {{Current_weight,Current_name,Previous_node}, Unvisited_nodes_updated} = gb_sets:take_smallest(Unvisited_nodes),
            case dict:is_key(Current_name,Paths) of
                false ->
                    io:format("loop_through_nodes: Found a new smallest unvisited node ~w~n",[Current_name]),

                    Paths_updated = dict:store(Current_name,{Previous_node,Current_weight},Paths),
                    io:format("loop_through_nodes: Updated Paths: ~w~n",[Paths_updated]),

                    Out_edges = digraph:out_edges(Graph,Current_name),
                    io:format("loop_through_nodes: Ready to iterate through the out edges of node ~w: ~w~n",[Current_name,Out_edges]),

                    Unvisited_nodes_updated_2 = loop_through_edges(Graph,Out_edges,Paths_updated,Unvisited_nodes_updated,Current_weight),
                    io:format("loop_through_nodes: Looped through out edges of the node ~w and updated Unvisited nodes: ~w~n",[Current_name,Unvisited_nodes_updated_2]),

                    loop_through_nodes(Graph,Paths_updated,Unvisited_nodes_updated_2);
                    true ->
                    loop_through_nodes(Graph,Paths,Unvisited_nodes_updated)
            end;
        true -> 
            Paths
    end.

loop_through_edges(Graph,[],Paths,Unvisited_nodes,Current_weight) ->
                    io:format("loop_through_edges: No more out edges ~n"),
    Unvisited_nodes;

loop_through_edges(Graph,Edges,Paths,Unvisited_nodes,Current_weight) ->
                    io:format("loop_through_edges: Start ~n"),
    [Current_edge|Rest_edges] = Edges,
    {Current_edge,Current_node,Neighbour_node,Edge_weight} = digraph:edge(Graph,Current_edge),
    case dict:is_key(Neighbour_node,Paths) of
        false ->
                    io:format("loop_through_edges: Inserting new neighbour node ~w into Unvisited nodes~n",[Current_node]),
            Unvisited_nodes_updated = gb_sets:insert({Current_weight+Edge_weight,Neighbour_node,Current_node},Unvisited_nodes),
                    io:format("loop_through_edges: The unvisited nodes are: ~w~n",[Unvisited_nodes_updated]),
            loop_through_edges(Graph,Rest_edges,Paths,Unvisited_nodes_updated,Current_weight);
        true ->
            loop_through_edges(Graph,Rest_edges,Paths,Unvisited_nodes,Current_weight)
    end.

Answer 1

您选择的数据结构看起来不错，因此主要是在其中插入什么内容以及如何使它们保持最新的问题。我建议如下（我稍微更改了名称）：

• Result：将 Node 映射到 的 dict {Cost, Prev}，其中 Cost 是到 Node 的路径的总成本，Prev 是路径上其前身.

• Open：{Cost, Node, Prev} 的 gb_sets 结构。

• 具有 {EdgeCost, NextNode} 形式的边的图。

搜索结果由 Result 表示，并且图表根本不更新。没有多重处理或消息传递。

算法如下：

• 在 Open 中插入 {0, StartNode, Nil}，其中 Nil 是标记结束的内容

• 令{{Cost, Node, Prev}, Open1} = gb_sets:take_smallest(Open)。如果 Node 已经在 Result 中，则不执行任何操作；否则将 {Cost, Node, Prev} 添加到 Result，并为 Node 的每条边 {EdgeCost, NextNode} > 将 {Cost + EdgeCost, NextNode, Node} 添加到 Open1，但前提是 NextNode 尚未在 Result.继续Open1，直到集合为空。

Dijkstra 算法要求对 Open 集执行 decrease_key() 操作。由于 gb_sets 不容易支持这一点，因此我们使用了为 NextNode 插入元组的解决方法，即使 NextNode 可能存在于 中>已经打开。这就是为什么我们检查从 Open 中提取的节点是否已在 Result 中。

---

优先级队列使用的扩展讨论 将

优先级队列与 Dijkstra 算法结合使用的方法有多种。

在维基百科的标准版本中，仅插入节点v一次，但当 v 的成本和前身发生更改时，v 的位置会更新。

alt := dist[u] + dist_between(u, v)
if alt < dist[v]:
    dist[v] := alt
    previous[v] := u
    decrease-key v in Q

通常通过用add v to Q替换decrease-key v in Q来简化实现。这意味着 v 可以添加多次，因此算法必须检查从队列中提取的 u 是否尚未添加到结果中。

在我的版本中，我将上面的整个块替换为 add v to Q。因此，队列将包含更多条目，但由于它们总是按顺序提取，因此不会影响算法的正确性。如果您不需要这些额外的条目，您可以使用字典来跟踪每个节点的最低成本。