Go言語で実装するダイクストラのアルゴリズム: 重み付きグラフでの最短経路探索

人は、生まれながらにして、ゴールが決まっている。

いつ、どこで、どのように死ぬのかが決まっているのだ。

問題はそれを最短経路で行くのか
遠回りしていくのか、だ。

死ぬ時期が決まっているのなら
そこに深みを持たせるしか価値は見出せない。

また、その経路も一つではない。

また、誰もどこがゴールかもわからない。

また、何に価値があるのかも決まっていない。

人生という名の迷路は
いかなるアルゴリズム、プログラムをもってしてでも解けないだろう。

ただ一つ、我々が幸運なことは
この迷路には行き止まりがないという事だ。

目次

1. ダイクストラのアルゴリズムとは
2. コード例
3. おわりに

1. ダイクストラのアルゴリズムとは

　ダイクストラ法（Dijkstra's algorithm）とは、様々な経路が考えられる二地点間の最短距離を求めるアルゴリズムの一つです。

　1959年にオランダのコンピュータ科学者エドガー・ダイクストラ（Edsger W. Dijkstra）によって考案されたアルゴリズムで、グラフ理論の基本的なアルゴリズムとしてよく知られてるそうです。

ダイクストラ法

　また、下記の記事が分かりやすかったです。
うさぎでもわかる離散数学

　簡単に書くと、

『ダイクストラのアルゴリズムは、重み付きグラフで一つのノードから他の全ノードへの最短経路を見つける方法で、最も近いノードから始めて、最短距離を一つずつ確定させていき、結果として、スタート地点から他の各ノードへの最短経路と距離が求められる』

というものになります。

2. コード例

　以下に実際に書いてみたコード例を示します。

　迷路を以下のような重み付きグラフとして表現します。

　各ノードは迷路の部屋または通路の交差点を表し、エッジは通路を表します。エッジの重みは通路を通過するのにかかる時間です。

A --1-- B --2-- C
|      /|       |
4     3 1       7
|   /   |       |
D --2-- E --1-- F
|               |
5               3
|               |
G --2-- H --1-- I

コード例

package main

import (
	"fmt"
	"math"
)

// Node はグラフのノードを表します。
type Node struct {
	name string
}

// Edge はグラフのエッジ（ノード間のつながり）を表し、重み（コストや距離など）を持ちます。
type Edge struct {
	node   *Node
	weight int
}

// Graph はノード（Node）とエッジ（Edge）の集まりです。
type Graph struct {
	nodes []*Node
	edges map[*Node][]*Edge
}

// NewGraph は新しいグラフを作成します。
func NewGraph() *Graph {
	return &Graph{
		nodes: []*Node{},
		edges: make(map[*Node][]*Edge),
	}
}

// AddNode はグラフに新しいノードを追加します。
func (g *Graph) AddNode(name string) *Node {
	node := &Node{name: name}
	g.nodes = append(g.nodes, node)
	return node
}

// AddEdge はグラフにエッジ（ノード間のつながり）を追加します。このエッジは重み（weight）を持ちます。
func (g *Graph) AddEdge(from, to *Node, weight int) {
	g.edges[from] = append(g.edges[from], &Edge{node: to, weight: weight})
	g.edges[to] = append(g.edges[to], &Edge{node: from, weight: weight}) // これは無向グラフのためのものです。
}

// String はグラフの内容を文字列として出力します。
func (g *Graph) String() {
	for _, node := range g.nodes {
		fmt.Printf("%s -> ", node.name)
		for _, edge := range g.edges[node] {
			fmt.Printf("%s (%d) ", edge.node.name, edge.weight)
		}
		fmt.Println()
	}
}

// Dijkstra はダイクストラのアルゴリズムを実行し、スタート地点から他の全ノードへの最短経路を計算します。
func Dijkstra(g *Graph, start *Node) (distances map[*Node]int, prev map[*Node]*Node) {
	distances = make(map[*Node]int)
	prev = make(map[*Node]*Node)

	// 初期化: 全ノードへの距離を無限大に設定します。
	for _, node := range g.nodes {
		distances[node] = math.MaxInt32
	}
	distances[start] = 0

	// 全ノードのリストを作成し、最短距離のノードを抽出します。
	nodes := make([]*Node, len(g.nodes))
	copy(nodes, g.nodes)

	for len(nodes) > 0 {
		// 最短距離のノードを取得します。
		minNode := nodes[0]
		minNodeIdx := 0
		for i, node := range nodes {
			if distances[node] < distances[minNode] {
				minNode = node
				minNodeIdx = i
			}
		}
		nodes = append(nodes[:minNodeIdx], nodes[minNodeIdx+1:]...)

		// 各隣接ノードの距離を更新します。
		for _, edge := range g.edges[minNode] {
			alt := distances[minNode] + edge.weight
			if alt < distances[edge.node] {
				distances[edge.node] = alt
				prev[edge.node] = minNode
			}
		}
	}
	return distances, prev
}

func main() {
	// グラフを作成します。
	g := NewGraph()

	// ノードを追加します。
	a := g.AddNode("A")
	b := g.AddNode("B")
	c := g.AddNode("C")
	d := g.AddNode("D")
	e := g.AddNode("E")
	f := g.AddNode("F")
	gg := g.AddNode("G") // gが使われており、競合を防ぐため'gg'を使用 
	h := g.AddNode("H")
	i := g.AddNode("I")


	// エッジ（ノード間のつながり）を追加します。
	g.AddEdge(a, b, 1)
	g.AddEdge(a, d, 4)
	g.AddEdge(b, c, 2)
	g.AddEdge(b, d, 3)
	g.AddEdge(b, e, 1)
	g.AddEdge(c, f, 7)
	g.AddEdge(d, e, 2)
	g.AddEdge(d, gg, 5)
	g.AddEdge(e, f, 1)
	g.AddEdge(f, i, 3)
	g.AddEdge(gg, h, 2)
	g.AddEdge(h, i, 1)

	// グラフの内容を出力します。
	g.String()

	// ダイクストラのアルゴリズムを実行します。
	distances, _ := Dijkstra(g, a)

	// スタート地点（A）から他の全ノードへの最短距離を出力します。
	for _, node := range g.nodes {
		if distances[node] != math.MaxInt32 {
			fmt.Printf("`スタート地点Aから%sへの最短距離は%dです。`\n", node.name, distances[node])
		} else {
			fmt.Printf("スタート地点Aから%sへの経路はありません。\n", node.name)
		}
	}
}

出力結果

A -> B (1) D (4) 
B -> A (1) C (2) D (3) E (1) 
C -> B (2) F (7) 
D -> A (4) B (3) E (2) G (5) 
E -> B (1) D (2) F (1) 
F -> C (7) E (1) I (3) 
G -> D (5) H (2) 
H -> G (2) I (1) 
I -> F (3) H (1) 
`スタート地点AからAへの最短距離は0です。`
`スタート地点AからBへの最短距離は1です。`
`スタート地点AからCへの最短距離は3です。`
`スタート地点AからDへの最短距離は4です。`
`スタート地点AからEへの最短距離は2です。`
`スタート地点AからFへの最短距離は3です。`
`スタート地点AからGへの最短距離は9です。`
`スタート地点AからHへの最短距離は7です。`
`スタート地点AからIへの最短距離は6です。`

簡単な解説

グラフのデータ構造

Node: ノード（グラフの各点）を表します。ここでは、name という文字列でノードを識別します。
Edge: エッジ（ノード間を結ぶ線）を表します。エッジは、どのノード（node）に接続しているかと、そのエッジの重み（weight、例えば通過にかかる時間など）を持っています。
Graph: グラフ全体を表します。グラフは複数のノード（nodes）と、各ノードに接続するエッジのリスト（edges）を持っています。

グラフの操作

AddNode: 新しいノードをグラフに追加します。
AddEdge: 二つのノード間に新しいエッジを追加します。このエッジは重み（weight）を持ちます。

ダイクストラのアルゴリズム

Dijkstra関数は、与えられたグラフとスタート地点のノードを引数に取り、スタート地点からグラフ内の各ノードへの最短経路を計算します。

プログラムの実行部分（main関数）

新しいグラフを作成し、9つのノード（AからI）を追加します。
ノード間にエッジを追加し、その重み（通過にかかる時間）を設定します。
グラフの内容を出力します。
ダイクストラのアルゴリズムを実行し、スタート地点（A）から各ノードへの最短経路を計算します。
計算結果を出力します。

ノードとエッジ、及びその具体例

ノード: グラフの各点です。このプログラムでは、A, B, C, ..., Iがノードです。
エッジ: 二つのノードを結ぶ線で、ノード間の関係を示します。エッジは重みを持ち、例えば通過にかかる時間などを表します。このプログラムでは、g.AddEdge(a, b, 1) はノードAとノードBを結ぶ重み1のエッジを追加しています。

3. おわりに

　便利なアルゴリズムが知れて良かったです。これから色々と使って行きたいです。