Akshay Patel Akshay Patel - 14 days ago 7
Java Question

Shortest path between 2 airports from waypoint to waypoint using dijktras algoritm (Java)

I am working on my final year computing project and need some advice/ help as I am not the most confident coder.

The project will create a software this uses an implementation of the Dijkstra’s algorithm to find the shortest path between airports. The software will allow the user to input a start airport and a destination airport within selected countries within European air space. The software will then draw the shortest path on an interactive map from waypoint to waypoint to the destination airport and additionally the route will be printed out in text will all relevant air navigation information. Additionally no fly zones can be inputted so that the path can be drawn around the no fly zone.

I am thinking of doing this in java but am confused on how to go about doing this for example, how do I get the map like google maps and then how do I add the airports and waypoints onto the graph as nodes.

Answer

As you've mentioned Google Maps I would recommend making this as a website using HTML/CSS/JavaScript. Everything you need to pull this kind of thing together already exists and it's all relatively straight forward too.

In terms of the steps you'll need to take, it will be roughly as follows:

1. Get a list of the airport information you want

Search query example: "JSON Airport information"

You'll need at least their latitude, longitude and airport code. A quick search pulled up this great looking project. Filter out the airports you don't want. Save the result as JSON, or just straight use one that's JSON already.

Add this information to your webpage by doing an ajax request - if you're new to JavaScript, most people use jQuery for that.

2. Figure out which map you want to use

You could use Google Maps, but there's so many other wonderful options like OpenLayers or anything that's based on it like MapBox. I'll be referencing OpenLayers because it's both free and a wonderfully easy project to get started with. Embed it on your site and then get to know its API. These API's are easy to understand and they provide lots of examples on how to show lines as well as markers (for the actual airports).

3. Display your airports

Using the map's API and your JSON data, put markers on the map however you'd like to display it. There's examples for flights too. The same applies to your no-fly zones; these map API's allow you to display areas too.

4. Perform your Dijkstra routing

There's a wide range of graph libraries for JavaScript. If you can't use a library for this, you can at least use them for inspiration. Use your airport information with a graph library that suits you to perform the searches you need. Finding the correct grand-circle distance can also be done with the map API, avoiding the need to implement that yourself. Use the distance as your dijkstra weights.

5. Add support for no-fly zones

This part of the question is a little vague as there's a lot of options here, as e.g. no-fly-zones have varying height and vehicle speed affects how the route should be planned. For example, it depends on if the vehicles are small drones or commercial aircraft. A simple approach is to just remove any routes which intersect your no-fly-zones; A quick search brought up this answer for help with that part. Alternatively research how routes are planned for your target vehicles and mimic that.