Skip to content

Instantly share code, notes, and snippets.

@eldilibra
Created October 23, 2014 06:49
Show Gist options
  • Save eldilibra/4745be9bcb5e64f44797 to your computer and use it in GitHub Desktop.
Save eldilibra/4745be9bcb5e64f44797 to your computer and use it in GitHub Desktop.
function Node (id, depth) {
this.id = id;
this.depth = depth;
this.children = [];
this.equals = function equals (otherNode) {
return this.id === otherNode.id;
};
}
function shortestPath (root, dest) {
var current = root;
var visited = [root];
var valid = [];
var counter = 0;
while (!current.equals(dest)) {
current.children.forEach(function (c) {
if (visited.indexOf(c) > -1) {
console.log('step #' + ++counter);
console.log('skipping', c.id, 'since it has been visited');
return;
}
console.log('step #' + ++counter);
console.log(c.id);
visited.push(c);
valid.push(c);
});
current = valid.shift();
}
}
var you = new Node("You", 0);
var a = new Node("a", 1);
var b = new Node("b", 1);
var c = new Node("c", 1);
var d = new Node("d", 2);
var e = new Node("e", 2);
var f = new Node("f", 3);
d.children.push(f);
c.children.push(d);
b.children.push(e);
b.children.push(c);
a.children.push(e);
a.children.push(b);
you.children.push(a);
you.children.push(b);
you.children.push(c);
shortestPath(you, f);
@eldilibra
Copy link
Author

Copy and paste this to a directory on your machine, then run node main.js. You'll see the traversal play out step by step.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment