majianyu
4/13/2018 - 2:24 AM

## dijkstras

``````graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}

# print(graph)

# the costs table
infinity = float("inf")
costs = {"a": 6, "b": 2, "fin": infinity}

# the parents table
parents = {"a": "start", "b": "start", "fin": None}

processed = []

# 找出开销最低的节点
def find_lowest_cost_node(costs: dict) -> str:
lowest_cost = float("inf")
lowest_cost_node = None
for node, cost in costs.items():
if cost < lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node

node = find_lowest_cost_node(costs)

while node is not None:
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys():
new_cost = cost + neighbors[n]
if costs[n] > new_cost:
costs[n] = new_cost
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs)
print(costs)
print(parents)
``````
``````package main

import (
"math"
"fmt"
)

var infinity = math.MaxInt64
var graph map[string]map[string]int
var costs map[string]int
var parents map[string]string
var processed map[string]bool

func init() {
graph = make(map[string]map[string]int)
graph["start"] = make(map[string]int)
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = make(map[string]int)
graph["a"]["fin"] = 1
graph["b"] = make(map[string]int)
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = make(map[string]int)

costs = make(map[string]int)
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

parents = make(map[string]string)
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = ""
processed = make(map[string]bool)
}
func main() {
foo()
for k, v := range costs {
fmt.Println(k, v)
}
for k, v := range parents {
fmt.Println(k, v)
}
}
func foo() {
// 获取开销最低的节点
node := findLowCostNode(costs)
// 循环
for node != "" {
// 获取该节点当前cost
cost := costs[node]
// 获取该节点所有邻居
neighbor := graph[node]
// 遍历邻居
for k, v := range neighbor {
//  新成本
newCost := cost + v
// 迭代新成本
if costs[k] > newCost {
costs[k] = newCost
parents[k] = node
}
}
// 标记已检查过该节点
processed[node] = true
// 重新获取开销最低的节点
node = findLowCostNode(costs)
}
}

// 找出开销最低的节点
func findLowCostNode(costs map[string]int) string {
lowCost := infinity
var lowNode string
for k, v := range costs {
if _, ok := processed[k]; !ok && lowCost > v {
lowCost = v
lowNode = k
}
}
return lowNode
}
``````