2021-04-21：手写代码：Dijkstra算法。

2021-04-21：手写代码：Dijkstra算法。

福大大 答案2021-04-21：

Dijkstra算法是一种基于贪心策略的算法。每次新扩展一个路程最短的点，更新与其相邻的点的路程。时间紧，未完成。

代码用golang编写。代码如下：

package main

import (
    "fmt"
    "math"
)

func main() {
    fmt.Println("")
}

func dijkstra1(from *Node) map[*Node]int {
    distanceMap := make(map[*Node]int)
    distanceMap[from] = 0
    // 打过对号的点
    selectedNodes := make(map[*Node]struct{})
    minNode := getMinDistanceAndUnselectedNode(distanceMap, selectedNodes)
    for minNode != nil {
        //  原始点  ->  minNode(跳转点)   最小距离distance
        distance := distanceMap[minNode]
        for _,edge := range minNode.edges {
            toNode := edge.to
            if _,ok:=distanceMap[toNode];!ok {
                distanceMap[toNode]= distance+edge.weight
            } else { // toNode
                distanceMap[edge.to]=getMin(distanceMap[toNode], distance+edge.weight))
            }
        }
        selectedNodes[minNode]= struct{}{}
        minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes)
    }
    return distanceMap
}
func getMin(a int,b int)int{
    if a<b{
        return a
    }else{
        return b
    }
}

func getMinDistanceAndUnselectedNode(distanceMap map[*Node]int, touchedNodes map[*Node]struct{}) *Node {
    var minNode *Node
    minDistance := math.MaxInt32
    for k, v := range distanceMap {
        node := k
        distance := v
        _, ok := touchedNodes[node]
        if !ok && distance < minDistance {
            minNode = node
            minDistance = distance
        }
    }
    return minNode
}

type Edge struct {
    weight int
    from   *Node
    to     *Node
}

// 点结构的描述
type Node struct {
    value int
    in    int
    out   int
    nexts []*Node
    edges []*Edge
}
type Graph struct {
    nodes map[int]*Node
    edges map[*Edge]struct{}
}

左神java代码