囲碁でヒープを使用してダイクストラの簡単な実装。

ダイクストラとは何か

メガ短い説明:ダイクストラのアルゴリズムは、AとBの間の最短パスを見つけるために、それは、最も遠い距離で未訪問のノードを選択し、それぞれの訪問していない隣人にそれを介して距離を計算し、より小さい場合は、隣人の距離を更新します.

未訪問のすべてのノードをマークします.未訪問のsetと呼ばれるすべての未訪問ノードの集合を作成します.この場合、訪問していないノードに対してsetを使用します.

すべてのノードに仮の距離値を割り当てます.初期ノードをカレントとして設定します.

現在のノードのための

は、その未訪問の隣人の全てを考慮して、現在のノードでそれらの仮の距離を計算します.現在の割り当てられた値に新しく計算された暫定距離を比較し、より小さいものを割り当てる.例えば、現在のノードAが6の距離でマークされて、隣人Bとそれをつなぐ端が長さ2を持つならば、Aを通してBまでの距離は6 + 2 = 8です.Bが以前より8より大きい距離でマークされたなら、8にそれを変えてください.さもなければ、現在の値を保ってください.

現在のノードの未訪問の隣人のすべてを考慮して、現在のノードを訪問したときにマークします.訪問したノードは再度チェックされません.

最も近い暫定距離でマークされた次の未訪問ノードを選択し、新しい「現在のノード」として設定し、ステップ3に戻る.

Wikipedia

ヒープは何ですか。

コンピュータ科学において、ヒープは基本的にヒーププロパティを満たすほとんど完全な木です:最大のヒープでは、どんな与えられたノードCのためにでも、PがCの親ノードであるならば、Pのキー(値)はCのキーより大きいか、Cのキーに等しいです.PのキーはCのキー以下である.ヒープの“top”(親なし)のノードはルートノードと呼ばれる.
Wikipedia
ヒープは、優先順位キューとして考えることができます最も重要なノードは常に上部にあり、削除されると、その置換が最も重要になります.これは、完全な順序で処理する特定のものを必要とするアルゴリズムをコーディングするときに便利です.しかし、完全なソートを実行したくない場合や、ノードの残りの部分について何かを知る必要がない場合.例えば、グラフの中でノード間の最短距離を見つけるためのよく知られたアルゴリズム、ダイクストラのアルゴリズムは、優先順位キューを使用して最適化することができます.
Cprogramming

なぜ？

私はグラフとそのアルゴリズムについて学ぶことを試みているので、私は大学に行ったことがないので、私はグラフについてあまり知らないので、私は私の自由な時間の中でこれを読んで、それを学ぶしようとするため、私は最近、ヒープを使用してPythonでダイクストラの1つの実装についてのビデオを見て面白かったので、私は同じことを行うことを決めた.
私は同じトピックについて多くの記事があります、そして、これらの記事が非常によくdijkstraまたは何がヒープであるかについて説明するということを知っていて、この記事は単に実装に集中する短い記事であるでしょう、私はあなたにゴングでヒープを使用しているダイクストラの非常に単純な実装を示したいです.
あなたがDjkstraについてもっと読みたいならば、あなたが私が見つけたこの記事を読むべきであることは驚くべきです.
An excelenct article

実装

ダイクストラは、2つのノード間の短いパスを探索するアルゴリズムであり、各ノードの隣人を訪問し、常に最小値を保っている原点ノードからのコストとパスを計算するアルゴリズムである.
まず、Min Hapを実装する必要があります.
パッケージヒープはヒープを実装する任意の型のヒープ操作を提供します.インターフェイス.ヒープは、各ノードがそのサブツリー内の最小値ノードであるプロパティを持つツリーです.
Godoc - heap
ヒープ.試み

package main

import hp "container/heap"

type path struct {
    value int
    nodes []string
}

type minPath []path

func (h minPath) Len() int           { return len(h) }
func (h minPath) Less(i, j int) bool { return h[i].value < h[j].value }
func (h minPath) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *minPath) Push(x interface{}) {
    *h = append(*h, x.(path))
}

func (h *minPath) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

type heap struct {
    values *minPath
}

func newHeap() *heap {
    return &heap{values: &minPath{}}
}

func (h *heap) push(p path) {
    hp.Push(h.values, p)
}

func (h *heap) pop() path {
    i := hp.Pop(h.values)
    return i.(path)
}

第二に、我々はグラフのロジックを実装する必要があるため、我々は、エッジを追加し、1つのノードからすべてのエッジを取得する機能を持つノード間のエッジを保つためにマップを含む構造体を使用する必要があります.
関数GetPathはダイジェクストラアルゴリズムを実装し、原点と運命の最短パスを取得します.
グラフ.試み

package main

type edge struct {
    node   string
    weight int
}

type graph struct {
    nodes map[string][]edge
}

func newGraph() *graph {
    return &graph{nodes: make(map[string][]edge)}
}

func (g *graph) addEdge(origin, destiny string, weight int) {
    g.nodes[origin] = append(g.nodes[origin], edge{node: destiny, weight: weight})
    g.nodes[destiny] = append(g.nodes[destiny], edge{node: origin, weight: weight})
}

func (g *graph) getEdges(node string) []edge {
    return g.nodes[node]
}


func (g *graph) getPath(origin, destiny string) (int, []string) {
    h := newHeap()
    h.push(path{value: 0, nodes: []string{origin}})
    visited := make(map[string]bool)

    for len(*h.values) > 0 {
        // Find the nearest yet to visit node
        p := h.pop()
        node := p.nodes[len(p.nodes)-1]

        if visited[node] {
            continue
        }

        if node == destiny {
            return p.value, p.nodes
        }

        for _, e := range g.getEdges(node) {
            if !visited[e.node] {
                // We calculate the total spent so far plus the cost and the path of getting here
                h.push(path{value: p.value + e.weight, nodes: append([]string{}, append(p.nodes, e.node)...)})
            }
        }

        visited[node] = true
    }

    return 0, nil
}

メイン.試み

package main

import (
    "fmt"
)

func main() {
    fmt.Println("Dijkstra")
    // Example
    graph := newGraph()
    graph.addEdge("S", "B", 4)
    graph.addEdge("S", "C", 2)
    graph.addEdge("B", "C", 1)
    graph.addEdge("B", "D", 5)
    graph.addEdge("C", "D", 8)
    graph.addEdge("C", "E", 10)
    graph.addEdge("D", "E", 2)
    graph.addEdge("D", "T", 6)
    graph.addEdge("E", "T", 2)
    fmt.Println(graph.getPath("S", "T"))
}

$ go run .
Dijkstra
12 [S C B D E T]

Github