Algorítmo de Dijsktra implementado em Node.JS e exemplo de utilização

dijsktra.js

const Fila = require('./Fila') // Importação de um algoritmo Fila

// Representação do grafo em Lista de Adjacência

// Exemplo de representação do grafo para o bom funcionamento do algoritmo
/* 
*  Os pares de valores contidos em ListaAdjacencia[i][j] 
*  representam o vertice de adjacência e o custo da aresta, 
*  simultaneamente 
*/
const ListaAdjacencia = [
    [[1, 50], [2, 30], [3, 100], [4, 10]],
    [],
    [[1, 5], [3, 50]],
    [[1, 20]],
    [[3, 10]]
]

// Implementação algoritmo Dijkstra

// grafo - lista de adjacencia; raiz - nó inicial; dest - nó de destino
function dijkstra(grafo, raiz, dest) {
    const distance = new Array(); // Lista de distancias entre vertices
    const visitados = new Array();// Vertices já visitados
    const filaPrioridade = new Fila([]); // Conjunto de valores cujos vértices ainda não contém o custo do menor caminho distance[v] determinado.

    // Realiza-se uma estimativa atribuindo infinito a todos os valores de distance
    // Marca todos os vertices visitados como false
    for (let v = 0; v < grafo.length; v++) {
        distance[v] = Infinity;
        visitados[v] = false;
    }
    distance[raiz] = 0; // O valor da distancia do nó raiz já é conhecido
    filaPrioridade.add([distance[raiz], raiz]); // Adiciona o custo do vertice e o vertice a fila

    while (!filaPrioridade.isEmpty()) { // Equanto a fila estiver cheia
        var p = filaPrioridade.getFirstItem(); // Primeiro item da fila. Neste caso um array de duas posiçoes
        var u = p[1]; // Pega o vertice que esta armazenado no primeiro item da fila
        filaPrioridade.remove(); // Indica que será atribuido ao vertice o custo do menor caminho

        if (visitados[u] == false) { // Verifica se o vertice ja foi visitado
            visitados[u] = true; // Marca o vertice como visitado
            for (let v = 0; v < grafo[u].length; v++) { // Para cada v adjacente a u
                var adj = grafo[u][v][0] // Seleciona o indice do vertice v adjacente a u
                var custoAresta = grafo[u][v][1] // Seleciona o valor da aresta de v adjacente a u

                // Relaxamento (u,v)
                // Se a distancia do vertice adjacente > a distancia do vertice marcado + o seu custo
                if (distance[adj] > (distance[u] + custoAresta)) {
                    distance[adj] = distance[u] + custoAresta // Atualiza o valor do adjacente
                    filaPrioridade.add([distance[adj], adj]) // Adiciona o custo do vertice adj e o vertice adj a fila
                }
            }
        }
    }

    /**
     * O retorno é um objeto contendo a menor distancia do nó raiz a todos os demais
     * e a menor distancia entre o nó raiz e o no destino
     */
    return { distanciaDeTodos: distance, distanciaDoDestino: distance[dest] }
}

// Exemplo de chamada da função e seu retorno... 
const resultado = dijkstra(ListaAdjacencia, 0, 3);
console.log("Distancias de todos os pontos = " + resultado.distanciaDeTodos)
console.log("Distancia de 0 a 3 = " + resultado.distanciaDoDestino)