Basic Dijkstra's Algorithm (assume same edge weights) https://www.youtube.com/watch?v=gdmfOwyQlcI

JS Solution

// thanks to:
// Adam - https://github.com/acreeger
// Juan - https://github.com/nilnullzip

// Note that I decided the search order heuristic should be based solely on the person being visited
// and the goal person. The position within the graph should not be considered, so the graph edges
// are not annotated. Rather a heuristic function is used that takes as input only two people. I believe
// this makes more sense if the heuristic is based on things like number of friends or similarity in
// things like: school, city, job, etc.

// class for graph

function Person (name, friends) {
	Person.id =3D Person.id || 0;
	this.id =3D Person.id++;
	this.name =3D name;
	this.friends =3D friends || {}; // List of Persons
	graph[this.id] =3D this;
}

Person.prototype.make_friends =3D function(f) {
	this.friends[f.id] =3D f;
	f.friends[this.id] =3D this;
	return this;
}

// Huristic function returns relative priority for searching
// Note: independent of graph, only depends on the two persons

function priority (a, b) {
	return 1;
}

// Breadth first search
// Algorithm based on visited and frontier nodes

function search(goal, frontier, visited) {
	visited =3D visited || {};
	frontier.sort(function(a,b){priority(a,b)}); // Search in order =
specified by huristic
	var next =3D {};
	for (i in frontier) { // Frontier is array
		person =3D frontier[i];
		if (person.id =3D=3D goal.id) {
			return 0; // Found goal!
		}
		visited[person.id] =3D person;
		for (var id in person.friends) { // Friends is hash with =
id as key
			if (!visited[id]) {
				next[id] =3D person.friends[id];
			}
		}
	}
	if (Object.keys(next).length=3D=3D0) {
		return Infinity; // No path to goal
	} else {
		var next_array =3D [];
		for (k in next) next_array.push(next[k]);
		return search(goal, next_array, visited) + 1;	// =
Recurse to next level in search
	}
}

// Very simple test

var graph =3D {}; // The entire graph
j =3D new Person("Juan");
a =3D new Person("Adam");
g =3D new Person("Greg");
j.make_friends(a);
g.make_friends(a);

var start =3D j;
var goal =3D g;

console.log("Juan and Greg are " + search(goal, [start], {}) + " levels =
apart")
console.log("\n\n-----------------------------\n\n")

// Adam's test data

graph =3D {}
var will =3D new Person("will");
var peter =3D new Person("peter");
var eric =3D new Person("eric");
var christina =3D new Person("christina");
var drew =3D new Person("drew")
var tori =3D new Person("tori")
var tobias =3D new Person("tobias")
var tris =3D new Person("tris")

tobias.make_friends(eric,5).make_friends(tori, 4);
tris.make_friends(tobias,7).make_friends(christina, 5)
christina.make_friends(peter, 4).make_friends(drew, 6)
drew.make_friends(peter, 8)
eric.make_friends(peter,8)
tori.make_friends(eric, 4)

console.log("How close are tris and peter?")
visited =3D {}
var levels =3D search(tris, [peter]);
console.log("They are %s level(s) apart.", levels)
console.log("\n\n-----------------------------\n\n")

console.log("How close are tris and drew?")
visited =3D {}
var levels =3D search(tris, [drew]);
console.log("They are %s level(s) apart.", levels)
console.log("\n\n-----------------------------\n\n")

console.log("How close are tori and christina?")
visited =3D {}
var levels =3D search(tori, [christina]);
console.log("They are %s level(s) apart.", levels)
console.log("\n\n-----------------------------\n\n")

console.log("How close are tris and will?")
visited =3D {}
var levels =3D search(tris, [will]);
console.log("They are %s level(s) apart.", levels)

Prompt

LinkedIn Connections. aka: degrees of separations.


Assume a social network.
Two people are signed up for your site, and you want to know how many people
are between them?


function getNumberOfNodesBetween(graph, node1, node2){

    return number;
}

getFriend(node) => array of all of a user's friends.

What is the time complexity?
What is the memory complexity?

BASIC:
Assume each connection has the same relative probability.

ADVANCED:
Assume each connection is assigned a relative probability of finding the other person?
    Wiki: Weighted Graph

Pseudo Solution

// Thanks to
// Kris

Assume a social network.
Two people signed for your site, how many first connections between them?


var graph = [ {node1:a, node2:c} ,{node1:c, node2:b}, {node1:c,node2:d}, {node1:d,node2:e}, {node1:c, node2:e}  ] ;


var A = {
    id : nameA,
    distance_array : [  {node:'c',distance:1}]
    distance_array : [  {node:'c',distance:1}, {node:'b',distance:2},
    distance_array : [  {node:'c',distance:1}, {node:'b',distance:2},  {node:d, distance:2}, {node:e, distance:2}  ]
},

var B = {
    id : nameb,
    distance_array : [ {c,1}, {} ]
}



function getNumberOfNodesBetween(graph, node1, node2) {

    var array1 = node1.distance_array;
    array1.forEach(function(obj){
   	 if (obj.node == node2) {
   		 return obj.distance;
   	 }
    });

}


getFriend(node) => array of all of a user's friends
getNumberOfNodesBetweeen(graph, A, B)

=== partial actual code==


var Node = function (name ) {
    this.id = name;
    this.distance_array = [];
}


var graph = [ {node1:a, node2:c} , {node1:e, node2:b} ,{node1:c, node2:b}, {node1:c,node2:d}, {node1:d,node2:e}, {node1:c, node2:e}  ] ;

var a = new Node("a");

var allNodes = [];
console.log("a =" + JSON.stringify(a));

var i =0;
for ( i = 0; i < graph.length; i++ ) {
    
    
    
}