Нахождение невзвешенного графа кратчайшего пути с использованием BFS (javascript) - PullRequest
Новая
       39

Нахождение невзвешенного графа кратчайшего пути с использованием BFS (javascript)

0 голосов
/ 20 октября 2018

Я пытаюсь применить BFS, чтобы найти длину кратчайшего пути в графике, но не совсем получаю правильный результат.

Я пытаюсь найти кратчайший путь, посещая каждый узел на графике;затем отметьте те, которые посещены, и продолжайте записывать длину пути.Я надеюсь вернуть массив, который содержит кратчайший путь, но я думаю, что я делаю что-то не так в этом процессе.

Я думаю, это как-то связано с тем, как я индексирую свои массивы и записываю свои расстояния.

Мой вход в настоящее время отформатирован в виде массива, который содержит соседей для каждой вершины i.Так, например, graph[i] даст вам массив соседей вершины i.

Любые мысли о том, как мне решить проблему, были бы очень полезны.Спасибо!

var shortestPathLength = function(graph) {
    let distances = []
    let pq = []
    distances[0] = 0 
    let mygraph = {}

    for (var i = 0; i<graph.length; i++) {
        distances[i] = -1
        mygraph[i] = graph[i]
    }


    pq.push(mygraph[0])

    while(pq.length > 0) {
        let min_node = pq.shift()
        for(var i = 0; i<min_node.length; i++) {
            candidate = distances[i] + 1
            if(distances[min_node[i]]== -1) {
                distances[min_node[i]] = distances[i] + 1
                 pq.push(graph[min_node[i]])
            }
            else if (candidate < distances[min_node[i]]) {
                distances[min_node[i]] = distances[i] + 1
            }

        }
    }

    function getSum(total, num) {
        return total + num;
    }

    console.log(distances)
    return distances.length

};

1 Ответ

0 голосов
/ 21 октября 2018

Ваша проблема candidate = distances[i] + 1.i - это индекс ребра внутри min_node, что совсем не интересно.То, что вы ищете, это текущее расстояние до min_node.Вам нужно будет либо назначить расстояние как свойство самого объекта min_node, либо сохранить идентификатор (индекс в graph) узлов в вашей очереди вместо самого объекта.

Я сделал несколько других упрощений, но единственной проблемой, связанной с демонстрацией пробежек в вашем коде, был поиск расстояния. 

function shortestPathLength = function(graph) {
    const distances = Array(graph.length).fill(-1);
    distances[0] = 0; // start node
    const queue = [0];

    while (queue.length > 0) {
        const node_index = queue.shift();
//                 ^^^^^
        const edges = graph[node_index]; // get the node itself
        const candidate = distances[node_index] + 1; // outside of the loop
//      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        for (const target in edges) {
            if (distances[target] == -1) {
                distances[target] = candidate;
                queue.push(target); // not graph[target]
//                         ^^^^^^
            }
        }
    }
    return distances;
}
...