最短経路問題
- グラフの二頂点間を結ぶ道のうち，辺の重重みの総和が最小になるものを求める問題
- 出発点と終点の取り方によって分類できる
- 出発点を一つ$S$に固定して，$S$から他の全ての頂点への最短経路を求める問題
- 全ての二頂点間の最短経路を求める問題
- 他にもいろんな問題設定がある
単一始点最短経路問題
- SSSP = Single Source Shortest Path
- Dijkstraアルゴリズムが有名
- 始点からの最小距離が確定している頂点集合を拡張していくような挙動で各頂点の最短距離を決定していく
procedure dijkstra;
V := 空集合;
U := 全ての頂点からなる集合;
vertex[始点].distance = 0;
for x := 始点以外の全ての頂点について do
vertex[x].distance = INF;
while Uが空集合でない do
p := Uの中でフィールドdisntanceの値が最も小さい頂点;
pをUから取り除きVに加える;
for pを始点とする辺それぞれについて do
x := 辺の終点
if xがUに属している then
vertex[x].distance = min(vertex[x].distance, vertex[p].distance + 辺の重み);
- ダイクストラ法の正しさは，「頂点集合$U$（最短経路が未確定）に属している頂点のうち，
distanceが最小の頂点$P$について，始点から$P$に至るまでの経路上の頂点は，頂点集合$V$（最短経路が確定）に属している頂点のみである」ことから示される - これは背理法を用いれば簡単に示せる
- もし，「$U$に属している頂点のうち
distanceが最小の頂点$P$に始点から至るまでの経路上に$V$に属していない（つまり$U$に属している）頂点$Q$が含まれる」と仮定すると，$Q$-$P$間の経路長を考慮すれば，「始点-$Q$」の経路の方が「始点-$P$」の経路より経路長が短いので，「$P$が$U$の中でdistanceが最小である」という仮定に矛盾する - つまり「始点からの最小距離が確定していない頂点集合の中で，
distanceが最小な頂点$X$」に至るまでの経路は，始点からの最小距離が確定している頂点のみを通る経路であるから，実は$X$は最小距離が確定した頂点集合$V$に入れることができて，$V$に新しい頂点$X$が入ったので$V$に属している頂点たちの最短距離をさらに小さくできる可能性があるので，更新する - $V$に属している頂点の
distanceには「$V$に属している頂点だけを通った時の最小距離」が記録されている - 初期状態で「$U$に属している集合のうち始点だけ
distanceを0にして，残りを$\infty$にする」ことで，上を自明に満たすようにしている - ダイクストラ法を適用するためには「頂点集合$U$（最短経路が未確定）に属している頂点のうち，
distanceが最小の頂点$P$について，始点から$P$に至るまでの経路上の頂点は，頂点集合$V$（最短経路が確定）に属している頂点のみである」ことが正しい必要があって，そのためには辺の重みが正であるという仮定が必要 - 「$U$が空集合でない間，一つ頂点を取り出して，$V$に入れる」とは「全ての頂点を一つづつ見る」ことと同じ
- 密なグラフなら隣接行列でグラフを表現する
- 疎なグラフなら隣接リストでグラフを表現する
- 下記の実装だと，頂点の個数を$n$とすると，最も内側の
forが$O(n)$でそれを$n$回まわすことになるので全体で$O(n^2)$になる
func Dijkstra(graph [][]int, start int) {
n := len(graph)
nodes := make([]node, n)
for i := 0; i < n; i++ {
nodes[i] = node{
id: i,
distance: INF,
hasVisited: false,
last: nil,
}
}
nodes[start].distance = 0
for step := 0; step < n; step++ {
var p int
mindis := INF
for x := 0; x < n; x++ { // ここでUに属している`distance`の最小な頂点を探して`p`に記録
if !nodes[x].hasVisited && nodes[x].distance < mindis {
p = x
mindis = nodes[x].distance
}
}
if mindis == INF {
log.Fatalln("Given graph is not connected one")
}
nodes[p].hasVisited = true // `p`を集合Vに入れる
for x := 0; x < n; x++ {
if nodes[p].hasVisited && nodes[p].distance + graph[p][x] < nodes[x].distance {
nodes[x].last = &nodes[p]
nodes[x].distance = nodes[p].distance + graph[p][x]
}
}
}
for _, node := range nodes {
if node.last == nil {
log.Printf("Node[%d]: %d, last: %d\n", node.id, node.distance, start)
} else {
log.Printf("Node[%d]: %d, last: %v\n", node.id, node.distance, node.last.id)
}
}
}
type node struct {
id int
distance int
hasVisited bool
last *node
}
- 辺の本数が頂点数に対して同じオーダーであるならば，グラフを隣接リストの形で持つ方が効率がいい
- ダイクストラ法で肝心なのは「集合$U$から
distanceが最小の頂点を見つけ出す」ところ - 最小値を効率的に求められるようなデータ構造ってなんかあったけな？？？
- あ，ヒープってのがあったな
- ヒープ：優先順位つき待ち行列（を配列上で表現したもの）
- Goにはヒープの実装が標準ライブラリで提供されてるよな？？？
// いんぷり
全対最短経路
- ダイクストラ法を全ての頂点に対して適用する
- これでも悪くない
- 他にもFloydのアルゴリズムがある