算法图解第7章——狄克斯特拉算法

前一章使用了广度优先搜索，它找出的是段数最少的路径。如果你要找出最快的路径，可使用狄克斯特拉算法。

狄克特斯拉算法，找出的是总权重最小的路径。用于每条边都有关联数字的图，这些数字叫做权重。

4个步骤：

1.找出最便宜的节点；

2.检查是否有前往它们的更短路径；

3.重复这个过程；

4.计算最终路径。

带权重的图称为加权图。

• 计算非加权图中的最短路径可以使用广度优先搜索；

• 而要计算加权图中的最短路径可使用狄克特斯拉算法，并且狄克特斯拉算法只适用于有向无环图，并且不能有负权重；

• 有负权边的图，可使用贝尔曼-福德算法。

例子：

//邻居节点
let graph = {}
graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2
graph['a'] = {}
graph['a']['fin'] = 1
graph['b'] = {}
graph['b']['fin'] = 5
graph['fin'] = {}
//开销
let costs = {}
costs['a'] = 6
costs['b'] = 2
costs['fin'] = 100000
//父节点
let parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['fin'] = ''
//记录处理过的节点
let processed = []
function getCosts(costs) {
    let node = findLowestCostNode(costs)
    while (node !== "") {
        cost = costs[node]
        neighbors = graph[node]
        for (var n in neighbors) {
            newCost = cost + neighbors[n]
            if (costs[n] > newCost) {
                costs[n] = newCost
                parents[n] = node
            }
        }
        processed.push(node)
        node = findLowestCostNode(costs)
    }
    return 'lowestCosts:' + costs['fin'];
}
function findLowestCostNode(costs) {
    lowestCosts = 1000000
    lowsetCostNode = ""
    for (var node in costs) {
        cost = costs[node]
        if (cost < lowestCosts && processed.indexOf(node) === -1) {
            lowestCosts = cost
            lowsetCostNode = node
        }
    }
    return lowsetCostNode
}
console.log(getCosts(costs));