Let’s tackle a complex problem in Geographic Information Science (GIS).
We will calculate the shortest paths between multiple cities and visualize these paths on a map.
Additionally, we will create a distance matrix and implement Dijkstra’s algorithm to compute the shortest path.
Problem Statement
- Input the latitude and longitude of multiple cities and calculate the distances between them using the Haversine formula.
- Create a distance matrix and use Dijkstra’s algorithm to compute the shortest path between specified cities.
- Visualize the shortest path on a map.
Step 1: Install Required Libraries
Install the necessary libraries in Google Colab.
1 | !pip install basemap |
Step 2: Import Libraries
Import the required libraries.
1 | import numpy as np |
Step 3: Define the Haversine Formula
Define the Haversine formula to calculate the distance between two points on the Earth’s surface.
1 | def haversine(lon1, lat1, lon2, lat2): |
Step 4: Define City Coordinates
Define the latitude and longitude of multiple cities.
1 | # City names and their coordinates (latitude, longitude) |
Step 5: Create a Distance Matrix
Calculate the distances between cities and create a distance matrix.
1 | # Get the list of cities |
Step 6: Create a Graph and Compute the Shortest Path
Use the networkx library to create a graph and compute the shortest path using Dijkstra’s algorithm.
1 | # Create a graph |
Step 7: Visualize the Shortest Path on a Map
Plot the shortest path on a map.
1 | # Create a map |
Explanation of Results
- Distance Matrix: The distances between each pair of cities are calculated and displayed as a matrix.
- Shortest Path: Dijkstra’s algorithm is used to compute the shortest path between specified cities.
For example, the shortest path from New York to Tokyo is displayed. - Map Visualization: The shortest path is plotted on the map as a blue line, and cities are marked with red dots.
Example Output
Distance Matrix:
1
2
3
4
5
6
7
8
9
10
11Distance Matrix (km):
[[ 0. 5570.22217974 10848.80799768 15988.75550704
12564.82836192]
[ 5570.22217974 0. 9558.71369496 16993.9334598
9671.00078916]
[10848.80799768 9558.71369496 0. 7826.61505774
14731.58984858]
[15988.75550704 16993.9334598 7826.61505774 0.
11011.66413128]
[12564.82836192 9671.00078916 14731.58984858 11011.66413128
0. ]]Shortest Path:
1
2
3Shortest path from New York to Tokyo:
New York -> Tokyo
Total distance: 10848.81 kmMap: The shortest path from New York to Tokyo via London is displayed as a blue line on the map.

This example demonstrates how to solve a complex problem in GIS by calculating shortest paths between multiple cities and visualizing them on a map.
This approach is useful for applications like route planning and network analysis.










