ダイクストラ法について

前回書いた幅優先探索では重みのついたグラフの最短経路をもとめることはできなかった。重みの付いたグラフの最短経路を求めるにはダイクストラ法を使う。

重みつきグラフ


こういうやつ

制限


負の重みつきのグラフは処理できない。負の重みつきの場合はベルマンフォード法を使う。

雑な考え方


各ノードのコストと親のノードを管理して開始ノードから未訪問の最短ノードに順次アクセスしていき、更新しまくる。

実装


前図を例とした場合…

  1. Aを開始ノード・Dを目的ノードとする
  2. 開始ノードAから最もコストの低いノードCを取得する
  3. そのノードCから隣接しているすべてのノードB, Dを取得する
  4. B, Dへの到達コストを更新し、それらの親ノードをCにする
  5. Cを訪問済みノードとして記録する
  6. 現状のノードAを基に未処理のノードがないか確認する。未処理のノードがある場合はそのノードを基準にして3以降の処理を繰り返す。ない場合はCのノードを基準にして3以降の処理を繰り返す

Scalaでの実装


そろそろ(筆者の能力的に)Scalaでの実装に限界感が出てきたものの、始めの図を無理やり実装してみたのが下記になる。たぶんあってる。あってるよな…???

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
import scala.collection.mutable

object DijkstrasAlgorithm extends App {

case class Node(name: String)

val sampleGraph: mutable.HashMap[Node, mutable.HashMap[Node, Double]] = mutable.HashMap(
Node("A") -> mutable.HashMap(Node("B") -> 6, Node("C") -> 2),
Node("B") -> mutable.HashMap(Node("D") -> 1),
Node("C") -> mutable.HashMap(Node("D") -> 7, Node("B") -> 3),
Node("D") -> mutable.HashMap()
)

// ノードまでのコストを記録する (StartをA、GoalをDとした場合)
val cost: mutable.HashMap[Node, Double] = mutable.HashMap(
Node("B") -> 6,
Node("C") -> 2,
Node("D") -> Double.PositiveInfinity
)

// 親ノードリスト (StartをA、GoalをDとした場合)
val parentNode: mutable.HashMap[Node, Node] = mutable.HashMap(
Node("B") -> Node("A"),
Node("C") -> Node("A"),
Node("D") -> Node("")
)

dijkstras(sampleGraph, Node("A") ,Node("D"), Seq())

def dijkstras(graph: mutable.HashMap[Node, mutable.HashMap[Node, Double]], currentNode: Node, goal: Node, visited: Seq[Node]): Unit = {

println(cost)
println(parentNode)

if (currentNode == goal) {
return
}

graph.get(currentNode) match {
case Some(x) => {
if (x.nonEmpty) {
// 最も近いノードを取得する
findShortestCostNode(x, visited) match {
case Some(sn) => {
// 最も近いノードの隣接ノードを取得し、順に処理する
getAdjacentNodes(graph, sn.head._1) match {
case Some(adjacentNodes) => {
for(an <- adjacentNodes.toList) {
if (cost(an._1) > cost(sn.head._1) + an._2) {
// 最短コストの更新
cost(an._1) = cost(sn.head._1) + an._2
// 親ノードの更新
parentNode(an._1) = sn.head._1
}
}
// 現状のノードの隣接ノードで未処理のノードがあるかどうか
findShortestCostNode(x, visited :+ sn.head._1) match {
// 未処理のノードがある場合はそちらのノードを基に探索する
case Some(nsn) => dijkstras(graph, currentNode, goal, visited :+ sn.head._1)
// ない場合は処理中の最も近いノードを次の探索の基準にする
case _ => dijkstras(graph, sn.head._1, goal, visited :+ sn.head._1)
}
}
case None => ???
}
}
}

}
}
case None => ???
}
}

// 隣接ノードのうち未訪問かつ最短コストのノードを取得
def findShortestCostNode(nodes: mutable.HashMap[Node, Double], visited: Seq[Node]): Option[mutable.HashMap[Node, Double]] = {
val node = nodes.filter(x => !visited.contains(x._1))
if (node.isEmpty) {
None
} else {
Option(mutable.HashMap(node.minBy(_._2)))
}
}

// 隣接ノードを取得する
def getAdjacentNodes(graph: mutable.HashMap[Node, mutable.HashMap[Node, Double]], node: Node): Option[mutable.HashMap[Node, Double]] ={
graph.get(node) match {
case Some(x) => Option(x)
case None => None
}
}

}

/*
過程
Map(Node(B) -> 6.0, Node(D) -> Infinity, Node(C) -> 2.0)
Map(Node(B) -> Node(A), Node(D) -> Node(), Node(C) -> Node(A))
Map(Node(B) -> 5.0, Node(D) -> 9.0, Node(C) -> 2.0)
Map(Node(B) -> Node(C), Node(D) -> Node(C), Node(C) -> Node(A))
Map(Node(B) -> 5.0, Node(D) -> 6.0, Node(C) -> 2.0)
Map(Node(B) -> Node(C), Node(D) -> Node(B), Node(C) -> Node(A))

結果
Map(Node(B) -> 5.0, Node(D) -> 6.0, Node(C) -> 2.0)
Map(Node(B) -> Node(C), Node(D) -> Node(B), Node(C) -> Node(A))

*/

参考書籍


なっとく! アルゴリズム