Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
var MAX_DEPTH = 3;
var findPath = function (source, target, u2f, visitor) { // u2f = user to friend
var dist = {}
var prev = {}
var queue = []
dist[source] = 0
prev[source] = source
queue[queue.length] = source
while (queue.length > 0) {
var cur = queue.shift() // pop the front element
var d = dist[cur]
if (cur == target) {
var path = []
var pos = target
while (prev[pos] != pos) {
path.unshift(pos)
pos = prev[pos]
}
visitor(source, target, path)
return d
}
if (d > MAX_DEPTH)
return d
var friends = u2f[cur]
for (var fi = friends.length; fi--; ) {
var next = friends[fi]
var nextd = next in dist ? dist[next] : 987654321 // inf
if (d + 1 < nextd) {
dist[next] = d + 1
prev[next] = cur
queue[queue.length] = next
}
}
}
return dist[target]
}
findPath;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.