Skip to content

Instantly share code, notes, and snippets.

@jpillora

jpillora/dijkstra.js

Last active December 11, 2024 17:45
Show Gist options
  • Save jpillora/7382441 to your computer and use it in GitHub Desktop.
Save jpillora/7382441 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. jpillora revised this gist Feb 28, 2014. 1 changed file with 105 additions and 59 deletions.
    164 changes: 105 additions & 59 deletions dijkstra.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,73 +1,119 @@
    //dijkstra solve graph starting at s
    function solve(graph, s) {
    var solutions = {};
    solutions[s] = [];
    solutions[s].dist = 0;
    while(true) {
    var parent = null;
    var nearest = null;
    var dist = Infinity;

    //for each existing solution
    for(var n in solutions) {
    var adj = graph[n];
    //for each of its adjacent nodes
    for(var a in adj) {
    //without a solution already
    if(solutions[a])
    continue;
    //choose nearest node with lowest cost
    var d = adj[a];
    if(d < dist) {
    //reference parent
    parent = solutions[n];
    nearest = a;
    dist = d;
    }
    }
    }

    //no more solutions
    if(dist === Infinity) {
    break;
    var solutions = {};
    solutions[s] = [];
    solutions[s].dist = 0;

    while(true) {
    var parent = null;
    var nearest = null;
    var dist = Infinity;

    //for each existing solution
    for(var n in solutions) {
    if(!solutions[n])
    continue
    var ndist = solutions[n].dist;
    var adj = graph[n];
    //for each of its adjacent nodes...
    for(var a in adj) {
    //without a solution already...
    if(solutions[a])
    continue;
    //choose nearest node with lowest *total* cost
    var d = adj[a] + ndist;
    if(d < dist) {
    //reference parent
    parent = solutions[n];
    nearest = a;
    dist = d;
    }

    //extend parent's solution path
    solutions[nearest] = parent.concat(nearest);
    //extend parent's cost
    solutions[nearest].dist = parent.dist + dist;
    }
    }

    //no more solutions
    if(dist === Infinity) {
    break;
    }

    return solutions;
    //extend parent's solution path
    solutions[nearest] = parent.concat(nearest);
    //extend parent's cost
    solutions[nearest].dist = dist;
    }

    return solutions;
    }

    //create graph
    var graph = {
    a: {e:1, b:1, g:3},
    b: {a:1, c:1},
    c: {b:1, d:1},
    d: {c:1, e:1},
    e: {d:1, a:1},
    f: {g:1, h:1},
    g: {a:3, f:1},
    h: {f:1}
    };

    var graph = {};

    var layout = {
    'R': ['2'],
    '2': ['3','4'],
    '3': ['4','6','13'],
    '4': ['5','8'],
    '5': ['7','11'],
    '6': ['13','15'],
    '7': ['10'],
    '8': ['11','13'],
    '9': ['14'],
    '10': [],
    '11': ['12'],
    '12': [],
    '13': ['14'],
    '14': [],
    '15': []
    }

    //convert uni-directional to bi-directional graph
    // needs to look like: where: { a: { b: cost of a->b }
    // var graph = {
    // a: {e:1, b:1, g:3},
    // b: {a:1, c:1},
    // c: {b:1, d:1},
    // d: {c:1, e:1},
    // e: {d:1, a:1},
    // f: {g:1, h:1},
    // g: {a:3, f:1},
    // h: {f:1}
    // };

    for(var id in layout) {
    if(!graph[id])
    graph[id] = {};
    layout[id].forEach(function(aid) {
    graph[id][aid] = 1;
    if(!graph[aid])
    graph[aid] = {};
    graph[aid][id] = 1;
    });
    }

    //choose start node
    var start = 'e';
    var start = '10';
    //get all solutions
    var solutions = solve(graph, start);


    console.log("From '"+start+"' to");
    //display solutions
    for(var s in solutions) {
    console.log(start + " -> " + s + ": [" + solutions[s].join(", ") + "] (dist:" + solutions[s].dist + ")");
    if(!solutions[s]) continue;
    console.log(" -> " + s + ": [" + solutions[s].join(", ") + "] (dist:" + solutions[s].dist + ")");
    }

    // e -> e: [] (dist:0)
    // e -> d: [d] (dist:1)
    // e -> a: [a] (dist:1)
    // e -> c: [d, c] (dist:2)
    // e -> b: [a, b] (dist:2)
    // e -> g: [a, g] (dist:4)
    // e -> f: [a, g, f] (dist:5)
    // e -> h: [a, g, f, h] (dist:6)
    // From '10' to
    // -> 2: [7, 5, 4, 2] (dist:4)
    // -> 3: [7, 5, 4, 3] (dist:4)
    // -> 4: [7, 5, 4] (dist:3)
    // -> 5: [7, 5] (dist:2)
    // -> 6: [7, 5, 4, 3, 6] (dist:5)
    // -> 7: [7] (dist:1)
    // -> 8: [7, 5, 4, 8] (dist:4)
    // -> 9: [7, 5, 4, 3, 13, 14, 9] (dist:7)
    // -> 10: [] (dist:0)
    // -> 11: [7, 5, 11] (dist:3)
    // -> 12: [7, 5, 11, 12] (dist:4)
    // -> 13: [7, 5, 4, 3, 13] (dist:5)
    // -> 14: [7, 5, 4, 3, 13, 14] (dist:6)
    // -> 15: [7, 5, 4, 3, 6, 15] (dist:6)
    // -> R: [7, 5, 4, 2, R] (dist:5)
  2. jpillora revised this gist Dec 23, 2013. 1 changed file with 23 additions and 7 deletions.
    30 changes: 23 additions & 7 deletions dijkstra.js
    View file
    Original file line number Diff line number Diff line change
    @@ -8,31 +8,39 @@ function solve(graph, s) {
    var nearest = null;
    var dist = Infinity;

    //for each existing solution
    for(var n in solutions) {
    var adj = graph[n];
    //for each of its adjacent nodes
    for(var a in adj) {
    //without a solution already
    if(solutions[a])
    continue;
    var len = adj[a];
    if(len < dist) {
    //choose nearest node with lowest cost
    var d = adj[a];
    if(d < dist) {
    //reference parent
    parent = solutions[n];
    nearest = a;
    dist = len;
    dist = d;
    }
    }
    }

    //no more solutions
    if(dist === Infinity) {
    break; //no solution
    break;
    }

    //extend parent's solution path
    solutions[nearest] = parent.concat(nearest);
    //extend parent's cost
    solutions[nearest].dist = parent.dist + dist;
    }

    return solutions;
    }

    //create graph
    var graph = {
    a: {e:1, b:1, g:3},
    @@ -44,14 +52,22 @@ var graph = {
    g: {a:3, f:1},
    h: {f:1}
    };

    //choose start node
    var start = 'e';
    //get all solutions
    var solutions = solve(graph, start);

    //display solutions
    for(var s in solutions) {
    console.log(start + " -> " + s + ": [" + solutions[s].join(", ") + "] (dist:" + solutions[s].dist + ")");
    }

    // e -> e: [] (dist:0)
    // e -> d: [d] (dist:1)
    // e -> a: [a] (dist:1)
    // e -> c: [d, c] (dist:2)
    // e -> b: [a, b] (dist:2)
    // e -> g: [a, g] (dist:4)
    // e -> f: [a, g, f] (dist:5)
    // e -> h: [a, g, f, h] (dist:6)
  3. jpillora created this gist Nov 9, 2013.
    57 changes: 57 additions & 0 deletions dijkstra.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,57 @@
    //dijkstra solve graph starting at s
    function solve(graph, s) {
    var solutions = {};
    solutions[s] = [];
    solutions[s].dist = 0;
    while(true) {
    var parent = null;
    var nearest = null;
    var dist = Infinity;

    for(var n in solutions) {
    var adj = graph[n];
    for(var a in adj) {
    if(solutions[a])
    continue;
    var len = adj[a];
    if(len < dist) {
    parent = solutions[n];
    nearest = a;
    dist = len;
    }
    }
    }

    if(dist === Infinity) {
    break; //no solution
    }

    solutions[nearest] = parent.concat(nearest);
    solutions[nearest].dist = parent.dist + dist;
    }

    return solutions;
    }

    //create graph
    var graph = {
    a: {e:1, b:1, g:3},
    b: {a:1, c:1},
    c: {b:1, d:1},
    d: {c:1, e:1},
    e: {d:1, a:1},
    f: {g:1, h:1},
    g: {a:3, f:1},
    h: {f:1}
    };

    //choose start node
    var start = 'e';
    //get all solutions
    var solutions = solve(graph, start);

    //display solutions
    for(var s in solutions) {
    console.log(start + " -> " + s + ": [" + solutions[s].join(", ") + "] (dist:" + solutions[s].dist + ")");
    }