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

user_7624223 0
Viewed 189

Here is a problem that can be modeled using a directed graph with different costs on each edge.

Our input is an array of edges.

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

['A', 'B', 20], meaning that from A to B the cost is 20. I wanted to write a function that returns the path between a given place to another place which has the minimal cost. Note that there is no cycles in this graph.

In this case, if the starting place is A and the destination is C then there are three ways to go

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

so the function should return the path that has the minimal cost which is A, B, D, C

Here is my attempt:

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]
}

So I use an adjacency list to represent the graph, i.e.

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

and then I use breadth first search to explore the graph and record the path and once we arrive at our destination we add the path to paths. Btw I am aware of Dijkstra algorithm, but, correct me if I am wrong, I feel like since this graph doesn't have a cycle so we can use a normal bfs to solve it.

My question is, my function actually has a bug where although it does capture all of the paths with its corresponding cost but the paths are not 100% correct. If you log out the return statement of the function i.e. paths.sort(([pathA, costA], [pathB, costB]) => costA - costB) you will see the value here is  [ [ 'A,B,D,C', 27 ], [ 'A,B,C', 30 ], [ 'A,B,C', 50 ] ]  . The first two are correct but the last one should be ['A','C', 50]. I think the problem is caused by the way to populate visited map but I cannot figure out how I can fix the problem.

breadth-first-search directed-graph algorithm javascript
1 Answers

Because you want to maintain separate path information for each possible path, even when one path intercepts another later, having a visited Map where the keys are destination nodes won't do the trick, since visited.set will overwrite previous paths' information.

Instead of using the visited to get the pointer in the loop at the end, I'd get the node info for the graph Map instead while iterating. Recursion will help.

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'));

user_95152070
Related