HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavascriptMinor

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

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewjavascriptasynchronousstackoverflowalgorithmjquery
problemsolvingthepathbitshortesttsptoolittle

Problem

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 t

Solution

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  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.

Code Snippets

//
                        }
                    }
                });
            }
        }
    });
}
// 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];
}
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
}

Context

StackExchange Code Review Q#61838, answer score: 4

Revisions (0)

No revisions yet.