|
Navigation Application with Mobile Telephony: Shortest-path
The Shortest Path Navigation Prototype Application The shortest path navigation application prototype aims to produce an application that calculates the shortest path or route between two different locations and return a map with the shortest route being highlighted to a WAP phone. The final product of the navigation application will then be added to the MapMe.com system [5] as an independent function. The term shortest path refers to the process of calculating the shortest path (route) between two points of the journey based on the distance of the road. Hence, the application prototype will only concentrate on the distance information that is the length of the road. One of the fundamental requirements of the navigation application is the type of maps that will be used. This prototype manipulates on digitised road maps as shown below.  Figure 3: Example of procured digitised road map (extracted from [25]) In finding the shortest path, the second important aspect of the application is the calculation of shortest path/route. The application accepts two input locations (i.e. the start address and the destination address) and then calculates the shortest path. In order to get a more accurate and precise calculation, two points are needed instead of just the road or street name(s). The shortest route will be illustrated and explained below.  Figure 4: Case A (map not to scale) In Figure 4, there are two highlighted streets i.e. Oxford Street and Canal Street. The start address will be from Oxford Street to the destination address at Canal Street. The numbers written in italic represents the distance (in kilometers) between two distinct junctions on the street. From the previous diagram (Case A), it is not feasible to get the shortest path between Oxford Street and Canal Street. The reason is there are various options of paths that can be taken to move from Oxford Street to Canal Street and moreover, the achievement of the shortest path depends on the exact start and destination locations. For instance, the shortest path navigation application might compute ‘Milan Road’ as the shortest path since this is the shortest distance between the two streets. And, this is inaccurate as the exact location of the user is being neglected. Due to the location sensor technology constraints in the project, another solution is implemented that is to include another parameter which the intersection of the roads (streets) also known as the junction. A point represents the junction. Two junctions will be needed which will define the two points namely, the start and destination points. Figure 5 shows an example of the implementation of the two points in terms of where the user is (near or at a junction) instead of merely using the road names. The location of the user are marked as ‘ ’. 
Figure 5: Case B (map not to scale) In this case, the shortest path can be best attained (as shown in Figure 5) and the result is better compared to the first case example. Lastly, the final displayed map will show the start and destination addresses and the highlighted shortest path. This map will be converted and saved in a format that is viewable on mobile phones. The next section addresses the algorithm employed to calculate the shortest path. The Shortest Path Algorithm The start and destination points can be represented as nodes as used in graphs. Therefore, a map can be considered as a graph with many nodes as shown in Figure 6.  Figure 6: Graphical representation By representing the map in a graphical format, the shortest path between two locations can be easily obtained, as there are various shortest path algorithms available such as Floyd’s algorithm [10], Bellman Ford algorithm [11], Topological Ordering algorithm [12], [21], A-Star algorithm [11] and Dijkstra’s algorithm [14]. As Dijkstra’s algorithm is the most commonly used and fast in terms of computation [14] therefore, the shortest path algorithm that is used to get the shortest path between two locations is the Dijkstra’s algorithm (as below).  Diagram 1: Dijkstra’s Algorithm |