Solution to Traveling Santa Problem

// Usage: 
// in the mongo shell,
// 'use' the database where the city data is loaded
// and execute the following lines
//
//
// load( "pathto/function.js");
// db.cities.find().forEach( buildEdges );
// findShortestPath();

function Path(){
this.distance = 0;
this.visited =  [];
this.clone = function() {
    var newPath = new Path();
    newPath.distance = this.distance;
    for ( i in this.visited )
        newPath.visited.push ( this.visited[i] );
    return newPath;
};
}

function compare( a, b ) {
    if (a.distance > b.distance )    
return 1;

    if( a.distance < b.distance )
        return -1;

    return 0;
};


function findShortestPath() {
    var path = new Path();
    path.visited.push( "North Pole" );
    path.distance = 0;
    var path = visit ( path );

    print( "Best path: { distance: "+path.distance+", path: ["+path.visited +" ] }" );
}


function visit ( path ) {
    // get last city visited
    var city = path.visited[ path.visited.length - 1 ];

    var paths = [];

    db.edges.find( { from: city } ).forEach (
        function( edge ) {
            // avoid cities I've already visited
            if ( path.visited.indexOf( edge.dest ) == -1 ) {

                // branch out a new path
                var newPath = path.clone();
                //print( "Adding the next edge "+edge.dest );
                newPath.visited.push( edge.dest );
                newPath.distance += edge.dist;

                //recurse
                paths.push( visit ( newPath ) );
            }
        }
    );

    if( paths.length == 0 ) {

        // if no new paths the tour is complete. Now go home!
        var lastEdge = db.edges.findOne(
            { from: path.visited[ path.visited.length -1 ],
              dest: path.visited[0]
            }
        );

        path.visited.push( path.visited[0] );
        path.distance += lastEdge.dist;

        print( "Path complete "+path.visited );
        paths.push( path );
    }
    
    paths.sort( compare );
    return paths[0];
}

// Functions for calculating distance

function Edge( from, dest, dist ) {
this.from =  from;
this.dest = dest;
this.dist = dist
}

function toRadians( degree ) {
    return degree * Math.PI / 180;
}

function haversine ( start, end ) {
    var lat1 = start[1];
    var lat2 = end[1];
    var lon1 = start[0];
    var lon2 = end[0];
    var R = 6371000;
    var φ1 = toRadians( lat1 );
    var φ2 = toRadians( lat2 );
    var Δφ = toRadians(lat2-lat1);
    var Δλ = toRadians(lon2-lon1);

    var a = Math.sin(Δφ/2) * Math.sin(Δφ/2) +
        Math.cos(φ1) * Math.cos(φ2) *
        Math.sin(Δλ/2) * Math.sin(Δλ/2);
    var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));

    var d = R * c;
    return d;
}

function buildEdges ( start )  {
    db.cities.find( { _id: { $ne: start._id } } ).forEach(
        function ( end ) { 
            var d = haversine( start.location.coordinates,  end.location.coordinates);
            db.edges.insert(  new Edge( start._id, end._id, d ) );
        }
    );    
}