We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Dijkstra: Shortest Reach 2
  5. Discussions

Dijkstra: Shortest Reach 2

Sort by

recency

|

471 Discussions

|

  • dehaka
     + 0 comments

    brute force dijkstra runs. fk priority queue.

    vector<pair<long, int>> shortestReach(int n, const vector<vector<pair<int, int>>>& edges, int s) {
    vector<bool> visited(n+1);
    vector<pair<long, int>> distance(n+1, {LONG_MAX, -1});
    distance[s] = {0, s};
    for (int count = 1; count <= n; ++count) {
        int shortest = -1;
        for (int i = 1; i <= n; ++i) {
            if (!visited[i] and (shortest == -1 or distance[shortest].first > distance[i].first)) shortest = i;
        }
        visited[shortest] = true;
        if (shortest == -1 or distance[shortest].first == LONG_MAX) break;
        for (auto neighbor : edges[shortest]) {
            int u = neighbor.first, W = neighbor.second;
            if (!visited[u]) distance[u].first = min(distance[u].first, distance[shortest].first + W);
        }
    }    
    return distance;
}

  • lucassanco2810
     + 0 comments

    What did the trick for me was reading this:

    "If there are edges between the same pair of nodes with different weights, they are to be considered as is, like multiple edges."

  • rodrigopscampos
     + 1 comment

    I couldn't find a way to pass test case #7 using python due to timeout. I tried all approaches from former posts that used to work, but no way. I overcome it rewriting the same algo in cpp and them it passed in the first attempt.

  • zoyashah41306
     + 0 comments

    GoPromotional products Dijkstra: Shortest Reach 2 is an innovative approach to solving the shortest path problem in graph theory, often used in computer science and network optimization. By implementing this algorithm, users can efficiently calculate the shortest path between two points in a graph, providing essential insights for routing, logistics, and data communication. This advanced solution ensures improved performance and speed for complex systems, making it a key tool for modern problem-solving.

  • vishnubabu94in
     + 0 comments

    js (solution using priority Q / heap)

    function heapMoveUp(hArr, indMap, distance, n) {
    let ind = indMap[n];
    while (ind > 0) {
        const p = ind - 1 >> 1;
        if (distance[hArr[p]] > distance[hArr[ind]]) { // comparison
            [hArr[p], hArr[ind]] = [hArr[ind], hArr[p]];
            indMap[hArr[p]] = p;
            indMap[hArr[ind]] = ind;
            ind = p;
        } else {
            break;
        }
    }
}
function heapMoveDown(hArr, indMap, distance, hSize, n) {
    let ind = indMap[n];
    while (ind < hSize) {
        let c = 2 * ind + 1;
        if (c >= hSize) break;

        const s = c + 1;
        if (s < hSize && distance[hArr[c]] > distance[hArr[s]]) { // comparison
            c = s;
        }

        if (distance[hArr[ind]] <= distance[hArr[c]]) break; // comparison

        [hArr[ind], hArr[c]] = [hArr[c], hArr[ind]];
        indMap[hArr[ind]] = ind;
        indMap[hArr[c]] = c;
        ind = c;
    }
}

function shortestReach(n, edges, s) {
    const graph = {};
    for (let i = 1; i <= n; i++) {
        graph[i] = {};
    }
    for (const [begin, end, weight] of edges) {
        if ((graph[begin][end] ?? Infinity) < weight) continue;
        graph[begin][end] = weight;
        graph[end][begin] = weight;
    }

    const result = {};
    const distance = { [s]: 0 };
    const indMap = {};
    const hArr = [];
    let hSize = 0;
    function insertHeap(n) {
        const ind = hSize;
        hArr[hSize++] = n;
        indMap[n] = ind;
        heapMoveUp(hArr, indMap, distance, n);
    }
    function deleteHeap() {
        const ret = hArr[0];
        hArr[0] = hArr[--hSize];
        delete indMap[ret];
        indMap[hArr[0]] = 0;
        heapMoveDown(hArr, indMap, distance, hSize, hArr[0]);
        return ret;
    }
    insertHeap(s);

    while (hSize > 0) {
        const nextShortest = deleteHeap();
        const minDis = distance[nextShortest];
        result[nextShortest] = minDis;

        for (const [node, weight] of Object.entries(graph[nextShortest])) {
            if (result[node] !== undefined) continue;

            const isInsert = distance[node] === undefined;
            const nDis = minDis + weight;
            if (isInsert) {
                distance[node] = nDis;
                insertHeap(node);
            } else if (distance[node] > nDis) {
                distance[node] = nDis;
                heapMoveUp(hArr, indMap, distance, node);
            }
        }
    }

    const ret = [];
    for (let i = 1; i <= n; i++) {
        if (i === s) continue;
        ret.push(result[i] ?? -1);
    }
    return ret;
}