Cacher is the code snippet organizer for pro developers

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
}