ダイクストラ法

キーワード

概要

非負の重み付きグラフの最短経路を求めるアルゴリズム。

探索の始点となる頂点から、各頂点への最短経路(のコスト)を求めるために用いる。

確定済みの点からからいける最短距離の点を確定済みにしていくことで、最短経路を求める。

点を確定する際に、その点に隣接する点の暫定距離が、確定済みの点を経由した場合の距離よりも大きい場合、暫定距離を更新する。

最短辺を探すためには、優先度付きキューを用いる。点を確定する際に、その点から隣接する頂点とその辺のコストのペアをキューに追加する。

計算量

グラフの頂点数を $N$ , 辺の数を $M$ とすると、 $\mathrm{O}(M\log{N})$

応用例

配達ルートの最適化

実装

頂点 1 からの最短経路を求める実装

func main() {
	var n, m int
	scanIntVariables(&n, &m)
	G := make([][][2]int, n+1)
	for i := 1; i <= n; i++ {
		G[i] = [][2]int{}
	}
	for i := 0; i < m; i++ {
		var a, b, c int
		scanIntVariables(&a, &b, &c)
		G[a] = append(G[a], [2]int{b, c})
		G[b] = append(G[b], [2]int{a, c})
	}
	D := make([]int, n+1) // 頂点1からの最短経路のコスト
	for i := 1; i <= n; i++ {
		D[i] = math.MaxInt64
	}
	D[1] = 0
	kakutei := make([]bool, n+1)
	q := priorityqueue.New[[2]int](func(a, b [2]int) int { return a[0] - b[0] })
	q.Push([2]int{D[1], 1})
	P := make(map[int]int) // コストのみを求める場合は不要
	for !q.Empty() {
		u := q.Pop()[1]
		if kakutei[u] {
			continue
		}
		kakutei[u] = true
		for _, e := range G[u] {
			v, c := e[0], e[1]
			if D[v] > D[u]+c {
				D[v] = D[u] + c
				q.Push([2]int{D[v], v})
				P[v] = u
			}
		}
	}
	u := n
	path := []int{} // 1からnまでの最短経路
	for u != 1 {
		path = append(path, u)
		u = P[u]
	}
}

例題

引用

クラスカル法ディニッツ法