ジュリアにおけるダイクストラのアルゴリズム

グラフ(指示された、または、指示されない)を与えられて、我々は距離計算の出発点として単一のソース・ノードからグラフのすべてのノードに最も短い経路を見つけたいです.
グラフは、このポストで使用される、それは方向づけられた重みグラフです:

以下に示す隣接行列のグラフを示します.

graph = [
          [0, 2, 4, 0, 0, 0],
          [0, 0, 1, 7, 0, 0],
          [0, 0, 0, 0, 3, 0],
          [0, 0, 0, 0, 0, 1],
          [0, 0, 0, 2, 0, 5],
          [0, 0, 0, 0, 0, 0],
        ];

さらに移動する前に、隣接行列上で読むことができ、参照のリンクを追加しました.

アルゴリズム
開始ノードまたはソース頂点を初期ノードと呼ぶ.最初のノードからy . dijkstraのアルゴリズムの距離は、最初の距離の距離をすることが無限の距離で始まるだろうと貪欲なアプローチで行われるように一歩一歩を改善しようとします.
1 )全てのノードをtreeset内で未訪問としてマークする.未訪問のsetと呼ばれるすべての未訪問ノードの集合を作成します.

# initial state of the six vertices, false as all unvisted
TreeSet = [ false, false, false, false, false, false] 

2)すべてのノードに暫定距離値を割り当てる.初期ノードに対して0に設定し、他のすべてのノードに対して無限大に設定する(初期ノード以外のすべてのノード距離がINFとして割り当てられるので、これはプログラムの出力で見ることができる).ノードVの暫定距離は、ノードVと出発ノードとの間に発見された最短経路の長さである.最初にパスがソース自体(それは長さ0の経路である)より他の頂点に知られていないので、他のすべての暫定距離は最初に無限大に設定されます.初期ノードをカレントとして設定します.

# initially dist is something like below:
dist = [ Inf, Inf, Inf, Inf, Inf, Inf]
# we know distance of starting node 1 from node 1 so
dist  = [0.0 , Inf, Inf, Inf, Inf, Inf]

3)現在のノードについては、全ての未来訪者を考慮し、現在のノードを介して仮の距離を計算する.現在の割り当てられた値に新しく計算された暫定距離を比較し、距離の配列で小さいものを割り当てる.これが緩和機構だ

# for our current node 1, node 2 and node 3 are connected 
# with distances being 2 and 4 respectively, others 
# stay Inf as those are not connected to current node.
dist = [0.0, 2.0, 4.0, Inf, Inf, Inf] # relaxation procedure

4)現在のノードの訪問していない隣人の全てを考慮したとき、現在のノードを訪問して(更新treeset)としてマークして、未訪問のセットからそれを取り除きます.訪問したノードは再度チェックされません.
5)目的地ノードが訪問されたとき(2つの特定のノードの間のルートを計画するとき)、または、訪問されていないセットのノードの間の最も小さな暫定距離が無限である(完全な横断を計画するとき、初期のノードと残りの未訪問のノードの間に接続がないとき、起こる)とき、止まってください.アルゴリズムが終了しました.
6)さもなければ、最も小さい暫定距離でマークされていない未訪問ノードを選択して新しい現在のノードとして設定し、ステップ3に戻る.

#consider the distances now
dist = [0.0, 2.0, 4.0, Inf, Inf, Inf] 
# so the next unvisted node with smallest tentative distance
# is node 2, so we change the current node to 2 and repeat 
# from step3

# for our current node 2, node 3 and node 4 are connected 
# with distances being 1 and 7 respectively, others 
# stay Inf as those are not connected to current node.
dist = [0.0, 2.0, 4.0, Inf, Inf, Inf] # before relaxation procedure

# After relaxation: [0.0, 2.0, 3.0, 9.0, Inf, Inf]
# Dist for updated from 4.0 to 3.0 as the according to step4,
# we check and update based on min(current_dist(node3), dist(node1-node2) + dist(node2-node3)) 
# so dist(1-2)+ dist(2-3) = 3.0 which is less than current distance of 4.0
# Dist for 4 -> as dist(node1-node2) + dist(node2-node4)

コード

# To find the vertex with
# minimum distance value, from the set of vertices
# not yet included in shortest path tree
function mindist(dist, sptset)
    min = Inf  # Initialize minimum distance for next node
    minindex = 0
    # Search smallest value nearest vertex not in the
    # shortest path tree
    for i in 1:size(graph)[1]
        if dist[i] < min && sptset[i] == false
            min = dist[i]
            minindex = i
        end
    end
    println("\nNext Node to be processed: ", minindex)
    return minindex
end

# Dijkstra's single source
# shortest path algorithm for a graph represented
# using adjacency matrix representation
function dijkstra(graph, initial_node)
    println("Source Node:", initial_node)
    println("Graph's Adjacency Matrix:\n", graph)
    TreeSet = [false for i in 1:size(graph)[1]] # step 1
    dist = [Inf for i in 1:size(graph)[1]] # step 2
    dist[initial_node] = 0

    for i in 1:size(graph)[1]

        # Pick the minimum distance vertex from
        # the set of vertices not yet processed.
        x = mindist(dist, TreeSet) # step 3
        println("Before relaxation: ", dist)

        # step 3 -> relaxation procedure
        # Update dist value of the adjacent vertices
        # of the picked vertex only if the current
        # distance is greater than new distance and
        # the vertex in not in the shortest path tree
        for j in 1:size(graph)[1]
            if graph[x][j] > 0 && TreeSet[j] == false && dist[j] > dist[x] + graph[x][j]
                dist[j] = dist[x] + graph[x][j]
            end
        end
        println("After relaxation: ", dist)

        # Put the minimum distance vertex in the
        # shortest path tree
        TreeSet[x] = true # step 4
    end
    println("v | d[v] ")
    println("---------")
    for (i , j) in enumerate(dist)
        println(i, " | ", j)
    end
end

graph = [
          [0, 2, 4, 0, 0, 0],
          [0, 0, 1, 7, 0, 0],
          [0, 0, 0, 0, 3, 0],
          [0, 0, 0, 0, 0, 1],
          [0, 0, 0, 2, 0, 5],
          [0, 0, 0, 0, 0, 0],
        ];

dijkstra(graph, 1)

出力:

(base) ashwani@user:~/practice$ julia dijkstra.jl
Source Node:1
Graph's Adjacency Matrix:
[[0, 2, 4, 0, 0, 0], 
 [0, 0, 1, 7, 0, 0], 
 [0, 0, 0, 0, 3, 0], 
 [0, 0, 0, 0, 0, 1], 
 [0, 0, 0, 2, 0, 5], 
 [0, 0, 0, 0, 0, 0]]

Next Node to be processed: 1
Before relaxation: [0.0, Inf, Inf, Inf, Inf, Inf]
After relaxation: [0.0, 2.0, 4.0, Inf, Inf, Inf]

Next Node to be processed: 2
Before relaxation: [0.0, 2.0, 4.0, Inf, Inf, Inf]
After relaxation: [0.0, 2.0, 3.0, 9.0, Inf, Inf]

Next Node to be processed: 3
Before relaxation: [0.0, 2.0, 3.0, 9.0, Inf, Inf]
After relaxation: [0.0, 2.0, 3.0, 9.0, 6.0, Inf]

Next Node to be processed: 5
Before relaxation: [0.0, 2.0, 3.0, 9.0, 6.0, Inf]
After relaxation: [0.0, 2.0, 3.0, 8.0, 6.0, 11.0]

Next Node to be processed: 4
Before relaxation: [0.0, 2.0, 3.0, 8.0, 6.0, 11.0]
After relaxation: [0.0, 2.0, 3.0, 8.0, 6.0, 9.0]

Next Node to be processed: 6
Before relaxation: [0.0, 2.0, 3.0, 8.0, 6.0, 9.0]
After relaxation: [0.0, 2.0, 3.0, 8.0, 6.0, 9.0]

v | d[v] 
---------
1 | 0.0
2 | 2.0
3 | 3.0
4 | 8.0
5 | 6.0
6 | 9.0

参考文献

Abdul Bari's Dijkstra Algorithm Explanation

To understand Adjacency Matrices

Dijkstra's Algorithm WikiPedia