Solving the Shortest Path problem (little bit of TSP, too)

Some background info:

I'm working at a shipping company and the company's web developer has been fired a week ago. My boss knew that I had some knowledge in web development, so until we get a new programmer, I'm developing the navigation web application.

What the application has to do:

Well it basically has to be able to calculate a route based on addresses from a spreadsheet file. What I have been developing is an "algorithm" to optimize this route to find the shortest one possible based on distance. There is one starting point and several end points ranging from 5 to 200.

The algorithm I came up with:

As I said above, we have an array of a starting point and several destinations, like this:

• start: Budapest, Hungary
• destination 1: Kecskemet, Hungary
• destination 2: Rackeve, Hungary
• destination 3: Vienna, Austria
• destination 4: Paris, France
• destination 5: Berlin, Germany

So from the starting point the route has to "visit" all these "waypoints". It doesn't matter which one is the last.

We are using the HERE platform as our data source.

Algorithm:

I am using this algorithm:

• check the distance from start to all of the destinations
• get the one with the smallest distance to start
• remove 1st destination (the one we took before) from the array and put it in the "optimized" array
• repeat, but change start to the last destination in the "optimized" array

Now I am pretty sure this is not a very good algorithm or anything, but I couldn't think better.

The main problem would be my code. It has been a few years since I used JS and jQuery, so I forgot almost everything, and I am pretty sure that I'm using everything wrong.

Here's my code

Documented with comments as I could do to figure out what does what:

function optimizedDrivingDirections(JSON) {
// The JSON variable has the location data in JSON format
// This is the array with the waypoints in order inside it
var optimizedArray = [];
// A variable for storing the response from the Matrix Routing API (which will give the distances between waypoints)
var response;
// Putting the starting point (always the first item in the JSON array) in the final array
optimizedArray.push(JSON[0]);
// Removing the first item from the JSON array
JSON.splice(0, 1);
// Constructing the API request call
var query = "http://route.nlp.nokia.com/routing/6.2/calculatematrix.json?app_code=" + _appCode + "&app_code=" + _appID + "&mode=fastest;car";
// Adding the starting point to the request. (3 is for latitude, 4 is for longitude).
query += "&start0=" + optimizedArray[0][3] + "," + optimizedArray[0][4];

// Adding the destinations to the query.
for (var i = 0; i < JSON.length - 1; i++) {
query += "&destination" + i + "=" + JSON[i + 1][3] + "," + JSON[i + 1][4];
}

// Making an AJAX call to a PHP file which will send a cURL request and get back the response from the API.
$.ajax({ url: 'php/matrixroutingrequest.php', type: 'POST', data: { 'app_code': _appCode, 'app_id': _appID, 'query': query }, success: function (data) { // This array will have the distances between the starting point and all of the other waypoints to select the closest one later. var distances = []; // Getting the response from the API call. response = jQuery.parseJSON(data); for (var i = 0; i < response.Response.MatrixEntry.length; i++) { // Adding all the distance data to the distances array. Note, that the response only returns distances, not the coordinates of the wapoints it belongs to. distances.push(response.Response.MatrixEntry[i].Route.Summary.Distance); } // Getting the index of the smallest distance from the distances array. var minindex = jQuery.inArray(Math.min.apply(this, distances), distances); // Adding the first closest waypoint to the optimized array optimizedArray.push(JSON[minindex + 1]); // Removing the waypoint from the JSON array (I have no idea why I have to add 1 to minindex, but it only works this way). JSON.splice(jQuery.inArray(JSON[minindex + 1], JSON), 1); // This is the loop for the rest of the distances and waypoints. for (var j = 0; j < JSON.length; j++) { // Constructing the request as before query = "http://route.nlp.nokia.com/routing/6.2/calculatematrix.json?app_code=" + _appCode + "&app_code=" + _appID + "&mode=fastest;car"; query += "&start0=" + optimizedArray[optimizedArray.length - 1][3] + "," + optimizedArray[optimizedArray.length - 1][4]; for (var k = 0; k < JSON.length; k++) { query += "&destination" + k + "=" + JSON[k][3] + "," + JSON[k][4]; } // Another AJAX request to the PHP file that gets info from the API for the next waypoint.$.ajax({
url: 'php/matrixroutingrequest.php',
type: 'POST',
data: {
'app_code': _appCode,
'app_id': _appID,
'query': query
},
success: function (data) {
// Constructing the request to the API call again.
query = "http://route.nlp.nokia.com/routing/6.2/calculatematrix.json?app_code=" + _appCode + "&app_code=" + _appID + "&mode=fastest;car";
query += "&start0=" + optimizedArray[optimizedArray.length - 1][3] + "," + optimizedArray[optimizedArray.length - 1][4];
for (var k = 0; k < JSON.length; k++) {
query += "&destination" + k + "=" + JSON[k][3] + "," + JSON[k][4];
}

// Another AJAX call to the PHP file, because for some reason the AJAX call from before kept repeating as if it was in a loop (ok, its in a loop, my bad, so this is pretty stupid here)
// Note that it's not async, it has to finish getting the distances before it continues running the code
$.ajax({ url: 'php/matrixroutingrequest.php', async: false, type: 'POST', data: { 'app_code': _appCode, 'app_id': _appID, 'query': query }, success: function (data) { response = jQuery.parseJSON(data); } }); // Obvious if (JSON.length > 1) { // Same thing as before, getting the distances and getting the smallest one, putting it in the optimized array and removing from JSON array var distances = []; for (var i = 0; i < response.Response.MatrixEntry.length; i++) { distances.push(response.Response.MatrixEntry[i].Route.Summary.Distance); } var minindex = jQuery.inArray(Math.min.apply(this, distances), distances); optimizedArray.push(JSON[minindex]); JSON.splice(jQuery.inArray(JSON[minindex], JSON), 1); } else { // IF it's the last waypoint, we'll push the last one into the optimized array and make JSON equal to the optimized array. optimizedArray.push(JSON[0]); JSON = optimizedArray; // Routing code ommited for clarity // // // // // } } }); } } }); }  Just by looking at my ugly code I have a headache. It's just so bad. Could some of you more experienced folks point out what should I do another way, and maybe give me some examples? It would help a lot! 1 Answer That is some ugly code indeed, but it can be rescued. The biggest problem seems to be that you have useless JSON calls and that you probably have a bug in there. The second biggest problem the code has is that everything is in 1 function, resulting in this at the end:  // } } }); } } }); }  I think in essence your code should simply keep popping the first entry of your JSON array, get distances from each remaining point to the popped entry and sort according to distances. This will also help you get rid of the copy pasted code for the first point: // Constructing the API request call var query = "http://route.nlp.nokia.com/routing/6.2/calculatematrix.json?app_code=" + _appCode + "&app_code=" + _appID + "&mode=fastest;car"; // Adding the starting point to the request. (3 is for latitude, 4 is for longitude). query += "&start0=" + optimizedArray[0][3] + "," + optimizedArray[0][4]; // Adding the destinations to the query. for (var i = 0; i < JSON.length - 1; i++) { query += "&destination" + i + "=" + JSON[i + 1][3] + "," + JSON[i + 1][4]; }  My counter proposal would be this: function getDistances( fromPoint , toPoints ){ var response; // Constructing the API request call var query = "http://route.nlp.nokia.com/routing/6.2/calculatematrix.json?app_code=" + _appCode + "&app_code=" + _appID + "&mode=fastest;car"; // Adding the starting point to the request. (3 is for latitude, 4 is for longitude). query += "&start0=" + fromPoint[3] + "," + fromPoint[4]; for (var i = 0; i < toPoints.length; i++) { query += "&destination" + i + "=" + toPoints[i][3] + "," + toPoints[i][4]; } //This is synchronous, it has to finish getting the distances before it continues running the code$.ajax({
url: 'php/matrixroutingrequest.php',
async: false,
type: 'POST',
data: {
'app_code': _appCode,
'app_id': _appID,
'query': query
},
success: function (data) {
var response = jQuery.parseJSON(data);
}
});
//Return what we came for
return response.Response.MatrixEntry.map( extractDistance );
}

function extractDistance( distanceResponseEntry  ){
return distanceResponseEntry.Route.Summary.Distance;
}

function sortByDistance( point1 , point2 ){
return point2 - point1;
}

function optimizedDrivingDirections(points) {

var route = [],
distances,
point;

while( points.length > 1 ){

point = points.shift();
route.push( point );

distances = getDistances( point , points );

for (var i = 0; i < distances.length; i++) {
points[i].distance = distances[i];
}
points.sort( sortByDistance );
}

route.push( points.pop() )
//Route has what you need
}


I consolidated all calls to calculatematrix.json into 1 function which takes a starting point and a list of end points ( fromPoint and toPoints ).

I have a specialized function to extract the distance from the API response so that getDistances looks cleaner.

I have a specialized sorter function so that you always have the shortest distance on top, so that you can keep shifting.

I renamed JSON to points, JSON is a terrible name. The reader wants to know what is provided, not in what format that data used to be. ( JSON is a string..)

I renamed optimizedArray to route, because that is what you are building in essence.

Since I dont have the full code there might be bugs in here (I could not test this at all), but the approach should be fairly straight forward.

From an algorithm perspective, you should read up on the 'travelling salesman' problem and see if the gained efficiency in routing (guaranteed shortest path) is worth the extra JSON calls you will need.