This project implements an optimized version of Dijkstra's shortest path algorithm for geographic information systems (GIS), such as those used in MapQuest and GPS-based navigation systems. The program computes the shortest route between cities on a map based on Euclidean distances and displays the route on a visual map interface.
- Interactive Map Interface: Select cities using mouse and keyboard inputs.
- Shortest Path Calculation: Finds and displays the lowest-cost route between two selected cities.
- Dynamic Route Display: The route is shown visually on the map.
- Optimized for Large Maps: Efficiently handles maps with at least 50 cities and thousands of edges.
- Map Preprocessing: Speeds up repeated shortest path queries by reusing previous computations.
The map is represented in a text file with the following structure:
Number of vertices (cities)
Number of edges (roads)
City1 Latitude1 Longitude1 0 (0 means this road cross)
City2 Latitude2 Longitude2 1 (1 means this city)
...
Edge1_City1 Edge1_City2
Edge2_City1 Edge2_City2
...
Example:
6
9
City1 31.52583 34.45250 1
City2 31.53389 35.09944 1
City3 31.52972 34.48139 1
City4 31.35611 34.30139 1
City5 31.90000 35.20417 1
cross1 31.70639 35.20167 0
City1 City2
City1 City4
City2 City3
City2 City5
City3 City5
City3 City4
City3 cross1
City4 cross1
City5 cross1
Upon launching the application, you will be greeted with the Welcome Screen. Here you can choose to
-
Choose Data manuale:
Selecting Upload data from xlsx file will open a file dialog where you can choose an xlsx file from your computer that contains the data ,then choose the image for map
-
Gaza Map:
You'll be prompted to choose the source city from ComboBox or click on it in the map, and the same for the destination city, then you click at Find button the shortest path will found
-
Palestine Map:
You'll be prompted to choose the source city from ComboBox or click on it in the map, and the same for the destination city, then you click at Find button the shortest path will found
