golangで最短路問題アルゴリズム3種(ベルマンフォード、ダイクストラ、ワーシャルフロイド)
TL;DR
競技プログラミングなどでよく使う、グラフの最短路問題のアルゴリズムをgolangで実装します。
例題として、AOJのシンプルな問題を使用しました。
onlinejudge.u-aizu.ac.jp
実装
1. ベルマンフォード法
特徴
- 負閉路があっても検出できる
- ダイクストラより遅い
- 実装簡単
ソース
下記を例題に対して実装します。 onlinejudge.u-aizu.ac.jp
package main import ( "bufio" "fmt" "math" "os" "strconv" ) type edge struct { to int // エッジ終点 w int // コスト } var inf = math.MaxInt32 func main() { sc := newScanner() v, e, r := sc.readInt(), sc.readInt(), sc.readInt() g := make([][]edge, v) for i := 0; i < e; i++ { s, t, d := sc.readInt(), sc.readInt(), sc.readInt() g[s] = append(g[s], edge{to: t, w: d}) } dist := make([]int, v) // 始点からの路長 for i := 0; i < v; i++ { dist[i] = inf // infで初期化 } // bellmanford dist[r] = 0 // スタートのノードの路長を0に更新 for i := 0; i < v; i++ { var updateFlg bool for j := 0; j < len(g); j++ { for _, edge := range g[j] { if dist[j] == inf { continue } // 路長を緩和 if dist[edge.to] > edge.w+dist[j] { updateFlg = true dist[edge.to] = min(dist[edge.to], edge.w+dist[j]) } } } // v回目のループで更新がある場合、負閉路があると判定 if i == v-1 && updateFlg { fmt.Println("NEGATIVE CYCLE") return } } // 各ノードへの最短路長を出力、到達不可の場合はINF for _, v := range dist { if v < inf { fmt.Println(v) } else { fmt.Println("INF") } } } func min(nums ...int) int { ret := nums[0] for i := 0; i < len(nums); i++ { if nums[i] < ret { ret = nums[i] } } return ret } // 入出力関連 type scanner struct { bufScanner *bufio.Scanner } func newScanner() *scanner { bufSc := bufio.NewScanner(os.Stdin) bufSc.Split(bufio.ScanWords) bufSc.Buffer(nil, 100000000) return &scanner{bufSc} } func (sc *scanner) readString() string { bufSc := sc.bufScanner bufSc.Scan() return bufSc.Text() } func (sc *scanner) readInt() int { bufSc := sc.bufScanner bufSc.Scan() text := bufSc.Text() num, err := strconv.Atoi(text) if err != nil { panic(err) } return num }
2. ダイクストラ法
特徴
- 負閉路があった場合は使えない
- ヒープ木を使う場合ベルマンフォードより速い
- ヒープ木を使う場合実装が少し複雑
※本ページの実装はヒープ木を使用
ソース
下記を例題にして実装します。 onlinejudge.u-aizu.ac.jp
package main import ( "bufio" "container/heap" "fmt" "math" "os" "strconv" ) type edge struct { to int // エッジ終点 w int // コスト } // ヒープで管理する要素情報 type vert struct { d int // 緩和したときのdistの値 v int // 緩和対象のノード番号 } // ヒープを表現するプライオリティキュー container/heap内のInterfaceを実装する type pQue []vert func (pq pQue) Len() int { return len(pq) } func (pq pQue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] } func (pq pQue) Less(i, j int) bool { return pq[i].d < pq[j].d } func (pq *pQue) Push(x interface{}) { *pq = append(*pq, x.(vert)) } func (pq *pQue) Pop() interface{} { x := (*pq)[len(*pq)-1] *pq = (*pq)[0 : len(*pq)-1] return x } var inf = math.MaxInt32 func main() { sc := newScanner() v, e, r := sc.readInt(), sc.readInt(), sc.readInt() g := make([][]edge, v) for i := 0; i < e; i++ { s, t, d := sc.readInt(), sc.readInt(), sc.readInt() g[s] = append(g[s], edge{to: t, w: d}) } dist := make([]int, v) // 始点からの路長 for i := 0; i < v; i++ { dist[i] = inf // infで初期化 } // dijkstra dist[r] = 0 // スタートのノードの路長を0に更新 var pq pQue heap.Push(&pq, vert{d: dist[r], v: r}) for len(pq) > 0 { mn := heap.Pop(&pq).(vert) if mn.d > dist[mn.v] { continue } for _, ed := range g[mn.v] { // 路長を緩和 if dist[ed.to] > dist[mn.v]+ed.w { dist[ed.to] = dist[mn.v] + ed.w heap.Push(&pq, vert{d: dist[ed.to], v: ed.to}) } } } for _, v := range dist { if v < inf { fmt.Println(v) } else { fmt.Println("INF") } } } func min(nums ...int) int { ret := nums[0] for i := 0; i < len(nums); i++ { if nums[i] < ret { ret = nums[i] } } return ret } // 入出力関連 type scanner struct { bufScanner *bufio.Scanner } func newScanner() *scanner { bufSc := bufio.NewScanner(os.Stdin) bufSc.Split(bufio.ScanWords) bufSc.Buffer(nil, 100000000) return &scanner{bufSc} } func (sc *scanner) readString() string { bufSc := sc.bufScanner bufSc.Scan() return bufSc.Text() } func (sc *scanner) readInt() int { bufSc := sc.bufScanner bufSc.Scan() text := bufSc.Text() num, err := strconv.Atoi(text) if err != nil { panic(err) } return num }
ヒープ木を取り扱うため、container/heapパッケージのInterfaceインタフェースを実装します。
上記ソースコードのpQueが実装になってます。
golang.org
3. ワーシャルフロイド法
特徴
- 全点体間最短路問題(グラフの全ての頂点の間の最短路を見つける問題)で使用する
- 負閉路検出できる
ソース
下記を例題にして実装します。 onlinejudge.u-aizu.ac.jp
package main import ( "bufio" "fmt" "math" "os" "strconv" "strings" ) var inf = math.MaxInt32 func main() { sc := newScanner() v := sc.readInt() e := sc.readInt() dp := make([][]int, v) //dp[i][j]はi-j間の最短路長を管理する for i := 0; i < len(dp); i++ { tmp := make([]int, v) for j := 0; j < len(tmp); j++ { if i == j { tmp[j] = 0 } else { tmp[j] = inf } } dp[i] = tmp } for i := 0; i < e; i++ { s, t, d := sc.readInt(), sc.readInt(), sc.readInt() dp[s][t] = d } // Warshall–Floyd for tmp := 0; tmp < v; tmp++ { for i := 0; i < v; i++ { for j := 0; j < v; j++ { // inf(到達不可)の場合は更新しない if dp[i][tmp] == inf || dp[tmp][j] == inf { continue } // tmpのノードを経由したほうが路長が短くなる場合、更新 dp[i][j] = min(dp[i][j], dp[i][tmp]+dp[tmp][j]) } } } // 出力 for i := 0; i < len(dp); i++ { // dp[i][i]が0未満の場合、負閉路ありと判断する if dp[i][i] < 0 { fmt.Println("NEGATIVE CYCLE") return } } for i := 0; i < len(dp); i++ { var s string for j := 0; j < len(dp[i]); j++ { if dp[i][j] == inf { s += "INF " } else { s += fmt.Sprintf("%d ", dp[i][j]) } } fmt.Println(strings.Trim(s, " ")) } } func min(nums ...int) int { ret := nums[0] for i := 0; i < len(nums); i++ { if nums[i] < ret { ret = nums[i] } } return ret } // 入出力関連 type scanner struct { bufScanner *bufio.Scanner } func newScanner() *scanner { bufSc := bufio.NewScanner(os.Stdin) bufSc.Split(bufio.ScanWords) bufSc.Buffer(nil, 100000000) return &scanner{bufSc} } func (sc *scanner) readString() string { bufSc := sc.bufScanner bufSc.Scan() return bufSc.Text() } func (sc *scanner) readInt() int { bufSc := sc.bufScanner bufSc.Scan() text := bufSc.Text() num, err := strconv.Atoi(text) if err != nil { panic(err) } return num }
実装自体はとても簡単です。 何をやっているのかは、下記の解説ページがとてもわかり易かったです。 qiita.com
システム障害が起こってしまったときのモチベーションの保ち方について
TL;DR
障害は悪だが、障害発生時には「障害は悪」という姿勢を一旦払拭すること。
導入
システム障害なんて、誰もが避けたいはず。
システムを利用しているユーザはもちろん、システムを提供しているベンダーは利用者への謝罪、即時復旧、即時復旧後も原因の追求であったり、恒久対策の検討、実施、その後も定期的な予後観察・・・
こんなの絶対関わりたくないと思っていても、エンジニアとして働いていれば必ず一度は直面することになる。
そういった状況下でのモチベーションの保ち方を考えてみた。
障害が発生した時のモチベーションの保ち方3つ
重く受け取りすぎない
対応時には、とんでもない障害が発生してしまった・・・と感じることでも、後々振り返ってみると、そうでもなかった、なんてことはザラにある。
おそらく、障害って基本的には突然やってくるものだから、その通常時との落差が錯覚させて何事も重く受け止めてしまうのだと思う。
重く受け取りすぎず、一旦深呼吸をして、脳内を下記のモードにスイッチしよう。
「貴重な経験だ」と考える
障害対応って、基本的にはイレギュラーなことなのだから、ある意味貴重な経験であることは間違いない。
自分をドラクエの主人公だと例えると、障害対応ははぐれメタルとの遭遇に似ている。
なかなか遭遇しないぶん、たおすとたくさん経験値がもらえる。
対応中は積極的に関わって、自分自身のエンジニア経験値の肥やしにしてやる、位の気概で取り組むことができれば、今後のためにもなりそう。
なお、一部始終を後々振り返られるように、何が原因で、どういう対応をしたか。また、こうしておけばもっと良かった、などは自分自身でちゃんと記録しておくべき。(対外向けの報告書とは別に、自分の言葉で書くのが大事。)
一体感を楽しむ
これの現象は人によるかもしれないが、
障害が発生したとき、チーム全体が「障害を解消する」という共通の目的意識を持つようになり、チームに一体感が生まれることがある。
こうなると、復旧対応や、嫌な顧客対応もなぜか楽しくなってくることがある。 こうなるともう無敵だと思う。
なお、この「一体化現象」はいつも発生するわけではなく、もともとのチームの文化に依存する。 普段からコミュニケーションが活発なチームほど、このパターンになりやすいと感じる。 チームのコミュニケーションの重要さは、普段の開発フェーズはもちろん、こういったところにも影響するのだと思う。
最後に
システムを提供する立場として、障害は悪であることに変わりはないし、普段からそういう気持ちで業務に臨む必要がある。
しかし、障害が起きないシステムなんて聞いたことはない。
障害が発生してしまったときは、上記の「障害は悪」モードを持ち続けるのではなく頭をスイッチして取り組むことが大事。
ブログテスト
ブログテスト
