🌲

gonum/graphを使って最短経路問題を解いてみた

2023/12/13に公開

概要

gonum/graphを使って最短経路問題を解いてみました。今回は、特に、"辺の重みが非負数の場合の単一始点最短経路問題"を対象とします。ですので、具体的にはDijkstra法で解くことになります。

実は、gonum/graphの中で、Dijkstra法を使って最小経路問題を解く関数はすでに実装されています。

gonum/graph自体を初めて使用するので、備忘録としてこの記事を書いています。graphを構築することからはじめて、Dijkstra関数を呼び出して最短経路を求めることをゴールとします。

Dijkstra法とは

Dijkstra法については、wikipediaやその他の記事を参考にしてください。

https://nw.tsuda.ac.jp/lec/dijkstra/

問題

例として次のようなグラフを考え、ノード0からノード4までの最短経路を求めます。

今回の最短経路は0 -> 1 -> 3 -> 4でその距離は3であることが簡単にわかります。

実装

先に全文を載せておきます。

main.go

package main

import (
	"fmt"
	"math"

	"gonum.org/v1/gonum/graph/path"
	"gonum.org/v1/gonum/graph/simple"
)

func main() {
	g := simple.NewWeightedUndirectedGraph(0, math.Inf(1))

	num := 5
	start := 0
	end := 4
	edges := [][]int{
		{0, 1, 1},
		{0, 2, 2},
		{1, 3, 1},
		{1, 2, 1},
		{2, 4, 3},
		{3, 4, 1},
	}

	for i := 0; i < num; i++ {
		node := simple.Node(i)
		g.AddNode(node)
	}

	for _, e := range edges {
		from := simple.Node(e[0])
		to := simple.Node(e[1])
		edge := g.NewWeightedEdge(from, to, float64(e[2]))
		g.SetWeightedEdge(edge)
	}

	shortest := path.DijkstraFrom(simple.Node(start), g)
	p, w := shortest.To(int64(end))
	for _, node := range p {
		fmt.Println(node.ID())
	}
	fmt.Println(w)
}

graphの構築

num := 5
start := 0
end := 4
edges := [][]int{
	{0, 1, 1}, // 始点, 終点, 重み
	{0, 2, 2},
	{1, 3, 1},
	{1, 2, 1},
	{2, 4, 3},
	{3, 4, 1},
}

初期化

まずグラフを初期化します。
graph/simpleパッケージにいろいろな種類のグラフの初期化用の関数があるようです。
今回は、重み付き無向グラフですので、NewWeightedUndirectedGraphを使用します。

g := simple.NewWeightedUndirectedGraph(0, math.Inf(1))

NewWeightedUndirectedGraphの第一引数は、自己ループの重み、第二引数はつながっていない辺の重みです。

ノードの追加

初期化したグラフにノードを追加していきます。

for i := 0; i < num; i++ {
	node := simple.Node(i)
	g.AddNode(node)
}

simple.NodeでIDのついたノードを作成します。
今回は簡単のために全て連番でIDをつけています。

辺の追加

辺を追加していきます。
始点と終点のノードを作成して、NewWeightedEdgeメソッドで辺を追加します。

*simple.WeightedUndirectedGraphを使用しているため、自動的に無向辺が生成されます。

for _, e := range edges {
	from := simple.Node(e[0])
	to := simple.Node(e[1])
	edge := g.NewWeightedEdge(from, to, float64(e[2]))
	g.SetWeightedEdge(edge)
}

Dijkstra

graph/pathパッケージのDijkstraFrom関数を使用して最短経路を取得します。

始点のノードを与えると、path.Shortestが返されるので、Toメソッドで終点を入力すると、(path []graph.Node, weight float64)が返されます。

shortest := path.DijkstraFrom(simple.Node(start), g)
p, w := shortest.To(int64(end))
for _, node := range p {
	fmt.Println(node.ID())
}
fmt.Println(w)

出力は次のようになります。

確かに最短経路である0 -> 1 -> 3 -> 4とその距離3が返されています。

まとめ

gonum/graphを利用することで自分で実装することなく最短経路問題が解くことができました。gonum/graphはAtCoderでも使用できるので、もし最短経路問題が出てきたら使用してみたいと思います。

概要

Dijkstra法とは

問題

実装

graphの構築

初期化

ノードの追加

辺の追加

Dijkstra

まとめ

Discussion