我們知道BFS廣度優(yōu)先算法只能用于查找段數(shù)最少的最有路徑也就是無權圖
如果對于有權圖BFS優(yōu)先算法就不適用了-使用Dijstra算法來解決加權圖的最短最有最小的問題
解決的有向正權圖對于負權圖這個算法不能解決-可以使用------貝爾曼-福德算法(Bellman-Ford algorithm)

我們使用下面的圖來介紹算法原理

微信圖片_20200117172914.png

用BFS算法我們得到的路徑可能是0-1-3或者0-2-3因為是段數(shù)最少的
下面介紹Dijstra算法的原理
節(jié)點權重圖

節(jié)點權重圖.png

1.從起點開始，找出到的最近的節(jié)點(權重最小的)B
2.查找他的鄰居節(jié)點的權重從B點到A點的最終開銷是2+3=5 小于權重圖到A點的6，我們就更新6為5
另一個鄰居終點2+5=7小于∞更新為7

微信圖片_20200117174953.png

3.重復第1和2步驟----->查找節(jié)點權重圖去除B以外的其他節(jié)點的
最后的圖變?yōu)?/p>

微信圖片_20200117175305.png

我們發(fā)現(xiàn)到達終點的權重最后為6
也就是從起點->B->A->終點

下面簡化一下步驟
1.找出最便宜的節(jié)點，也就是最短時間到達的節(jié)點
2.查找該節(jié)點的鄰居，查找是不是有前往鄰居的更近的節(jié)點，有就更新節(jié)點
3.重復上面的兩個步驟，遍歷所有的節(jié)點
4.計算最終的路徑

算法實現(xiàn)
1.需要一個有向圖結構
2.除去起點的所有節(jié)點的權重圖的散列表
3.需要一個除去起點的所有節(jié)點的父節(jié)點的散列表

數(shù)據(jù)結構也是可以優(yōu)化的，不做討論
有向帶權圖的初始化

package main

import (
    "fmt"
    "math"
    "strconv"
)

// 邏輯不是很嚴謹  越界的沒考慮-- scanf

// 邊節(jié)點結構
type EdgeTableNode struct {
    index         int            // 頂點索引
    weight        int            // 權重
    edgeTableNode *EdgeTableNode // 下一個臨界點的指針
}

// 頂點的數(shù)據(jù)信息
type VertInfo struct {
    value int
    name  string
}

// 頂點節(jié)點
type VertNode struct {
    vertInfo      VertInfo //  定點的數(shù)據(jù)信息
    edgeTableNode *EdgeTableNode
}

type Graph struct {
    vertNum  int
    grapType uint8
    edgeNum  int

    hasCircle bool
    allCircle [][]int
    visted    []int

    vertNode []*VertNode
}

var arrayList []int

func NewGraph(vertNum int, edgeNum int, grapType uint8) *Graph {
    return &Graph{vertNum: vertNum, hasCircle: false, allCircle: [][]int{},
        visted: make([]int, vertNum), grapType: grapType,
        edgeNum: edgeNum, vertNode: []*VertNode{}}
}

// 只做了有向圖的初始化
// 沒考慮無向圖
func (this *Graph) InitGrap() {
    // 頂點初始化
    for i := 0; i < this.vertNum; i++ {
        vert := &VertNode{}

        vert.vertInfo.value = i
        vert.vertInfo.name = "V" + strconv.Itoa(i)

        fmt.Println(*vert)

        this.vertNode = append(this.vertNode, vert)
    }

    // 邊初始化
    var startVert int
    var endVert int
    var weight int
    var n int
    for i := 0; i < this.edgeNum; i++ {
        n, _ = fmt.Scanf("%d %d %d", &startVert, &endVert, &weight)

        fmt.Printf("%d %d %d\n", startVert, endVert, n)

        var edgeNode = this.vertNode[startVert].edgeTableNode
        if edgeNode == nil {
            tempNode := new(EdgeTableNode)
            tempNode.weight = weight
            tempNode.index = endVert
            tempNode.edgeTableNode = nil
            this.vertNode[startVert].edgeTableNode = tempNode
            continue
        }

        for edgeNode != nil {
            // 單鏈表尾插節(jié)點
            if edgeNode.edgeTableNode == nil {
                tempNode := new(EdgeTableNode)
                tempNode.weight = weight
                tempNode.index = endVert
                tempNode.edgeTableNode = nil
                edgeNode.edgeTableNode = tempNode
                break
            }

            edgeNode = edgeNode.edgeTableNode
        }
    }
}

算法的核心代碼

// 獲取權重最低的節(jié)點
// 不能包含已經搜索過的
func (this *Graph) MinCostsNode(costs map[int]float64) int {
    minCostIndex := -1

    inf := math.Inf(1)
    
    for key, value := range costs {
        // 已經被查找過
        if this.visted[key] == 1 {
            continue
        }

        if value < inf {
            minCostIndex = key
            inf = value
        }
    }
    return minCostIndex
}

func (this *Graph) Dijkstra(start, end int) []int {
    if start >= this.vertNum || start < 0 || end >= this.vertNum || end < 0 {
        return nil
    }
    // 除起點外所有要到達的節(jié)點的對應權重
    mapCosts := make(map[int]float64)
    // 從哪個節(jié)點到這個節(jié)點的映射關系
    // key值與上面的mapCosts一樣
    mapParent := make(map[int]float64)

    // 匿名函數(shù)初始化
    func() {
        //
        for i := 0; i < this.vertNum; i++ {
            if i == start {
                node := this.vertNode[i]
                edgeNode := node.edgeTableNode
                for edgeNode != nil {
                    mapCosts[edgeNode.index] = float64(edgeNode.weight)
                    mapParent[edgeNode.index] = float64(i)
                    edgeNode = edgeNode.edgeTableNode
                }

                continue
            }

            // 其他非起點的鄰居節(jié)點設置為∞
            if _, ok := mapCosts[i]; !ok {
                mapCosts[i] = math.Inf(0)
                mapParent[i] = math.Inf(0)
            }
        }
    }()

    minCostIndex := this.MinCostsNode(mapCosts)
    for minCostIndex != -1 {
        // 獲取他的鄰接點
        node := this.vertNode[minCostIndex]
        // 獲取他的所有鄰接點
        edgeNode := node.edgeTableNode
        for edgeNode != nil {
            // 如果到達鄰接點的權重+最小權重的值小于鄰接點的權重就更新  起點到達鄰接點的權重
            tempCost := float64(edgeNode.weight) + mapCosts[minCostIndex]
            if tempCost < mapCosts[edgeNode.index] {
                mapCosts[edgeNode.index] = tempCost
                // 更新父節(jié)點
                mapParent[edgeNode.index] = float64(minCostIndex)
            }

            // 查找剩余的鄰接點
            edgeNode = edgeNode.edgeTableNode
        }

        // 當前節(jié)點已經處理過了
        this.visted[minCostIndex] = 1
        minCostIndex = this.MinCostsNode(mapCosts)
    }

    var path []int

    // 逆序遍歷出路徑
    if math.IsInf(mapParent[end], 0) {
        return path
    }

    // 查找路徑
    path = append(path, end)
    value := int(mapParent[end])
    for value != start {
        path = append(path, value)
        value = int(mapParent[value])
    }

    path = append(path, start)

    // 是逆序的尋路點
    // 可以倒序得到順序的節(jié)點
    fmt.Println(path)
    return path
}

main函數(shù)測試代碼
測試的圖用的是上面的第一幅圖來測試

func GrapDijstra() {
    var grap = NewGraph(4, 5, 1)
    grap.InitGrap()

    grap.Dijkstra(0, 3)
}

func main() {
    //GrapDfs()
    //GrapTuoPuSort()
    //GrapBfs()
    GrapDijstra()
}

輸入奇數(shù)行是輸入-偶數(shù)行書打印的日志
0 1 6
0 1 3
0 2 2
0 2 3
1 3 1
1 3 3
2 1 3
2 1 3
2 3 5
2 3 3

結果
[3 1 2 0]