JavaScript 算法 : print out the path from directed graph with minimal costs

Question

这是一个可以使用在每条边上具有不同成本的有向图来建模的问题。

我们的输入是一个边数组。

const edges = [['A', 'B', 20], ['B', 'C', 10], ['A', 'C', 50], ['B', 'D', 5], ['D', 'C', 2]]

['A', 'B', 20], 表示从 A 到 B 的成本是 20。我想编写一个函数，返回给定地点与成本最低的另一个地点之间的路径。请注意，此图中没有循环。

在这种情况下，如果起点是A，终点是C，那么有3条路可以走

path 1: A => C - cost 50
path 2: A => B => C - cost 30
path 3: A => B => D => C - cost 27

所以函数应该返回具有最小成本的路径，即 A, B, D, C

这是我的尝试:

function bar(edges, start, end) {
    const paths = []
    const visited = new Map()
    const graph = edges.reduce((map, [start, end, cost]) => {
        if(map.has(start)) {
            map.get(start).push([end, cost])
        } else {
            map.set(start, [[end, cost]])
        }
        return map
    }, new Map())
    const queue = [[start, 0]]
    for(const [node, costSofar] of queue) {
        if(node === end) {
            let pointer = node
            const path = []
            while(pointer) {
                path.push(pointer)
                pointer = visited.get(pointer)
            }    
            
            paths.push([path.reverse().join(','), costSofar])
            continue
        }
        graph.get(node).forEach(([dest, localCost]) => {
            // this part 👇 is problematic
            visited.set(dest, node)
            queue.push([dest, localCost + costSofar])
            
        })
    }

    return paths.sort(([pathA, costA], [pathB, costB]) => costA - costB)[0]
}

所以我用邻接表来表示图，即

{
    A: [['B', 20], ['C', 50]]
    B: [['C', 10], ['D', 5]]
    D: [['C', 2]]
}

然后我使用广度优先搜索来探索图形并记录路径，一旦我们到达目的地，我们就将路径添加到 paths。顺便说一句，我知道 Dijkstra 算法，但是，如果我错了，请纠正我，我觉得因为这个图没有循环，所以我们可以使用普通的 bfs 来解决它。

我的问题是，我的函数实际上有一个错误，虽然它确实捕获了所有具有相应成本的路径，但路径并非 100% 正确。如果您注销函数的返回语句，即 paths.sort(([pathA, costA], [pathB, costB]) => costA - costB) 您将看到此处的值为 ‹[ [ 'A,B,D,C', 27 ], [ 'A,B,C', 30 ], [ 'A,B,C', 50 ] ]‹ .前两个是正确的，但最后一个应该是 ['A','C', 50]。我认为问题是由填充 visited map 的方式引起的，但我不知道如何解决这个问题。

Answer 1

因为您希望为每条可能的路径维护单独的路径信息，即使一条路径稍后拦截另一条路径，拥有一个 visited 键是目标节点的 Map 也无法解决问题，因为 visited.set 将覆盖之前路径的信息。

我不是在最后使用 visited 获取循环中的指针，而是在迭代时获取 graph Map 的节点信息。递归会有所帮助。

function bar(edges, start, end) {
    const graph = edges.reduce((map, [start, end, cost]) => {
        if(map.has(start)) {
            map.get(start).push([end, cost])
        } else {
            map.set(start, [[end, cost]])
        }
        return map
    }, new Map())
    const paths = [];
    const find = (start, pathSoFar = [start], costSoFar = 0) => {
        for (const [dest, cost] of graph.get(start)) {
            const newPath = pathSoFar.concat(dest);
            if (dest === end) {
                paths.push([newPath.join(','), costSoFar + cost]);
            } else {
                find(dest, newPath, costSoFar + cost);
            }
        }
    };
    find(start);
    
    console.log(paths);
    
    // return paths.sort(([pathA, costA], [pathB, costB]) => costA - costB)[0]
    // or, make it O(n) instead of O(n log n):
    return paths.reduce((a, b) => a[1] > b[1] ? b : a);
}
const edges = [['A', 'B', 20], ['B', 'C', 10], ['A', 'C', 50], ['B', 'D', 5], ['D', 'C', 2]]

console.log(bar(edges, 'A', 'C'));