Elixirでダイクストラ法を実装してみました

この記事ではダイクストラ法アルゴリズムをElixirで実装したものをご紹介します

目次

1. バージョン情報
2. 目的
3. グラフと実装コード
4. 実行結果
5. 得られた経験
6. 所感
7. 参考文献

バージョン情報

Elixir: 1.8.1

目的

Elixirとダイクストラ法の勉強と満足感を得るために実装してみました

グラフと実装コード

グラフ

画像にすると読み込み遅くなると思って文字にしました。

                 #######   13   #######        11
        -------->#  A  #------->#  D  #-------------------
        |        #######        #######                  |
      8 |           |____      _____↑                    |
        |                | 1  | 9                        |
        |                ↓    |                          ↓
    #########    3      #######   15   #######   12   #######
    # start #---------->#  B  #------->#  E  #-------># fin #
    #########           #######        #######        #######
        |            ____↑   |____                       ↑
        |           | 5           | 4                    |
      2 |           |             ↓                      |
        |        #######   7    #######        20        |
        -------->#  C  #------->#  F  #-------------------
                 #######        #######

実装コード

以下実装コードです。与えているinitGraph(), initCosts(), initParents()は初期値です。

    defmodule Dijkstra do
      def initGraph do
            graph = %{
                "start" => %{
                    "a" => 5,
                    "b" => 2
                },
                "a" => %{
                    "d" => 4,
                    "c" => 2,
                },
                "b" => %{
                    "a" => 8,
                    "c" => 7
                },
                "c" => %{
                    "fin" => 1
                },
                "d" => %{
                    "c" => 6,
                    "fin" => 3
                },
                "fin" => %{}
            }

            graph
        end

        def initCosts do
            costs = %{
                "a"   => 5,
                "b"   => 2,
                "c"   => 99999999,
                "d"   => 99999999,
                "fin" => 99999999
            }

            costs
        end

        def initParents do
            parents = %{
                "a" => "start",
                "b" => "start",
                "c" => nil,
                "d" => nil,
                "fin" => nil
            }

            parents
        end

        def main do
            graph   = initGraph()
            costs   = initCosts()
            parents = initParents()
            processed = []

            lowest_cost_node = find_lowest_cost_node(costs, processed)

            {costs, parents} = search_all_neighbor_node(lowest_cost_node, costs, graph, parents, processed)

            print_path_and_each_cost(costs, parents)
        end

        def print_path_and_each_cost(costs, parents) do
            parent_node = parents["fin"]

            path = [{"fin", costs["fin"]}]

            path = fin_to_start_path_and_eachcost(costs, parent_node, path, parents)

            Enum.reverse(path)
        end

        def fin_to_start_path_and_eachcost(_, "start", path, _) do
            path = path ++ [{"start", 0}]

            path
        end

        def fin_to_start_path_and_eachcost(costs, parent_node, path, parents) do
            path = path ++ [{parent_node, costs[parent_node]}]

            parent_node = parents[parent_node]

            fin_to_start_path_and_eachcost(costs, parent_node, path, parents)
        end

        def find_lowest_cost_node(costs, processed) do
            lowest_cost = 99999999
            lowest_cost_node = nil

            find_lowest_cost_node(costs, costs |> Map.keys, processed, lowest_cost, lowest_cost_node)
        end

        def find_lowest_cost_node(costs, [ node_ | remain_costs ], processed, lowest_cost, lowest_cost_node) do
            cost = costs[node_]

            lowest_cost_node =
            if cost < lowest_cost && !(node_ in processed) do
                node_
            else
                lowest_cost_node
            end

            if remain_costs == [] do
                lowest_cost_node
            else
                find_lowest_cost_node(costs, remain_costs, processed, costs[lowest_cost_node], lowest_cost_node)
            end
        end

        def search_all_neighbor_node(nil, costs, _, parents, _) do
            {costs, parents}
        end

        def search_all_neighbor_node(node, costs, graph, parents, processed) do
            cost = costs[node]
            neighbors = graph[node]

            neighbors_keys = neighbors |> Map.keys

            if neighbors_keys == [] do

                processed = processed ++ [node]

                node = find_lowest_cost_node(costs, processed)

                search_all_neighbor_node(node, costs, graph, parents, processed)
            else
                [n | remain_neighbors] = neighbors_keys

                {costs, parents} = update_costs_and_parents(cost, neighbors, [ n | remain_neighbors ], costs, parents, node)

                processed = processed ++ [node]

                node = find_lowest_cost_node(costs, processed)

                search_all_neighbor_node(node, costs, graph, parents, processed)
            end

        end

        def update_costs_and_parents(cost, neighbors, [ n | remain_neighbors ], costs, parents, node) do
            new_cost = cost + neighbors[n]
            {new_cost, new_parent} =
            if costs[n] > new_cost do
                {new_cost, node}
            else
                {costs[n], parents[n]}
            end

            costs   = %{costs | n => new_cost}
            parents = %{parents | n => new_parent}

            if remain_neighbors == [] do
                {costs, parents}
            else
                update_costs_and_parents(cost, neighbors, remain_neighbors, costs, parents, node)
            end
        end
    end

実行結果

    Erlang/OTP 21 [erts-10.3.1] [source] [64-bit] [smp:2:2] [ds:2:2:10] [async-threads:1] [hipe]

    Interactive Elixir (1.8.1) - press Ctrl+C to exit (type h() ENTER for help)
    iex(1)> c "Dijkstra.exs"
    [Dijkstra]
    iex(2)> Dijkstra.main
    [{"start", 0}, {"b", 3}, {"d", 12}, {"fin", 23}]
    iex(3)>

得られた経験

• Mapから最小値の取得が案外難しいことが分かりました
  • 組み込みモジュール探したけどなかったので実装しました（もしかして存在する…？）
• レキシカルスコープの雰囲気を体験できました
  • 要するにdoと対応するendまでがスコープですね！
• 関数の宣言順番は重要
• ダイクストラ法と仲良くなった気がする満足感を得られました

所感

• Youtubeで関係ない動画見ながら実装していたら３日ぐらいかかりました。参考文献にはwhileを使用していたのですが、Elixirにはwhileがないので再帰関数で実装しました。再帰関数むずかしぃ。
• コード行が結構なものなりました。気が向いたら改善していきたいと思います。

参考文献

• なっとく！アルゴリズム
• プログラミングElixir