Skip to content

Instantly share code, notes, and snippets.

@rickkk856

rickkk856/Dijkstra Algorithm & Google Maps.ipynb

Last active July 14, 2025 12:07
Show Gist options
  • Save rickkk856/6eb2083ab376868c03752fd9d7f7ae62 to your computer and use it in GitHub Desktop.
Save rickkk856/6eb2083ab376868c03752fd9d7f7ae62 to your computer and use it in GitHub Desktop.
Download ZIP
Uses GPS location to get the shortest path between points and generate a map on Google Maps, does not use Directions API so it doesn't consider the road lenth (only strainght distance)
Display the source blob
Display the rendered blob
Raw
Dijkstra Algorithm & Google Maps.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "Shortest_Path_Dijkstra",
"provenance": [],
"collapsed_sections": []
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "DUDvDKUujcYe"
},
"source": [
"## **This code gets GPS positions to calculate the shortestp path using the Dijkstra Algorithm.** \n",
"\n",
"However, it does not consider the lenth of the roads, it just calculates the distance in a straight line. The benefit is that you don't need to have a Google Maps direction API to use it. So it works well in examples where you need to know the shortest path in multiple cities in the same region or in cases you can move straight foward\n",
"\n",
"\n",
"[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/drive/1kQQJURH90uSCePmVzYTzKFYYrCU4OYLv?usp=sharing)\n",
"\n",
"\n",
"[Source Code](https://stackoverflow.com/questions/59230049/find-the-shortest-distance-between-sets-of-gps-coordinates-python)\n",
"\n",
"[Directions API](https://developers.google.com/maps/documentation/directions/quickstart)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "Wjjh29hulwfB"
},
"source": [
"GPS VARIABLES EXAMPLES"
]
},
{
"cell_type": "code",
"source": [
"# CASO Viagem produtos do paraguay [Foz do Iguaçu, Curitiba, Florianopolis, São Paulo, Porto Alegre]\n",
"GPS = [[-25.537893, -54.553493],\n",
" [-25.452700, -49.267116],\n",
" [-27.593742, -48.543424],\n",
" [-23.550821, -46.644826],\n",
" [-30.040061, -51.217238],\n",
" ]\n",
"\n",
"print(\"www.google.com.br/maps/dir/-25.4527,-49.267116,2/-27.593742,-48.543424,3/-23.550821,-46.644826,4/-30.040061,-51.217238,5/-25.537893,-54.553493,1/\")"
],
"metadata": {
"id": "C2763j-dB8uE",
"colab": {
"base_uri": "https://localhost:8080/"
},
"outputId": "d6decf94-bb77-4ad2-9ba6-8efb47927f9c"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"www.google.com.br/maps/dir/-25.4527,-49.267116,2/-27.593742,-48.543424,3/-23.550821,-46.644826,4/-30.040061,-51.217238,5/-25.537893,-54.553493,1/\n"
]
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "zbh4xo_nkvVV",
"colab": {
"base_uri": "https://localhost:8080/"
},
"outputId": "74cfde13-877b-4db8-9305-8de03c6b8f33"
},
"source": [
"# CASO Distribuição de vacinas nas regiões metropolitanas do paraná [Curitiba, Ponta Grossa, Londrina, Maringá, Apucarana, Guarapuava, Cascavel, Foz do Iguaçu, Umuarama, Paranavai --> Curitiba]\n",
"GPS = [[-25.470538, -49.265299],\n",
" [-25.069671, -50.164804],\n",
" [-23.286567, -51.178127],\n",
" [-23.419820, -51.940818],\n",
" [-23.549300, -51.456034],\n",
" [-25.403297, -51.491502],\n",
" [-24.953373, -53.450593],\n",
" [-23.753024, -53.310948],\n",
" [-23.067313, -52.467429],\n",
" ]\n",
"\n",
"print(\"https://www.google.com.br/maps/dir/-23.5493,-51.456034/-23.286567,-51.178127/-23.41982,-51.940818/-23.067313,-52.467429/-25.403297,-51.491502/-23.753024,-53.310948/-25.069671,-50.164804/-24.953373,-53.450593/-25.470538,-49.265299/@-24.2529899,-52.4798602,8z/data=!3m1!4b1!4m2!4m1!3e0\")"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"https://www.google.com.br/maps/dir/-23.5493,-51.456034/-23.286567,-51.178127/-23.41982,-51.940818/-23.067313,-52.467429/-25.403297,-51.491502/-23.753024,-53.310948/-25.069671,-50.164804/-24.953373,-53.450593/-25.470538,-49.265299/@-24.2529899,-52.4798602,8z/data=!3m1!4b1!4m2!4m1!3e0\n"
]
}
]
},
{
"cell_type": "code",
"metadata": {
"id": "yh2_rWF7jngw",
"colab": {
"base_uri": "https://localhost:8080/"
},
"outputId": "155cff2d-952a-4c82-aa2c-f6886ce5c63c"
},
"source": [
"# CASO Viagem distribuição de produtos região leste sudeste [São Paulo, Campinas, Rio de Janeiro, Belo Horizonte, Vitória, Ribeirão Preto, Governador Valadares, São Paulo]\n",
"GPS = [[-23.555728, -46.662584],\n",
" [-22.817303, -47.069732],\n",
" [-22.986072, -43.210891],\n",
" [-19.810498, -43.977416],\n",
" [-20.361883, -40.299458],\n",
" [-21.181180, -47.791368],\n",
" [-18.872015, -41.957341],\n",
" [-23.555728, -46.662584],\n",
" ]\n",
"\n",
"print(\"https://www.google.com.br/maps/dir/-22.817303,-47.069732/-23.555728,-46.662584/-23.555728,-46.662584/-21.18118,-47.791368/-22.986072,-43.210891/-19.810498,-43.977416/-18.872015,-41.957341/-20.361883,-40.299458/@-21.5437532,-47.4932151,6.25z\")"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"https://www.google.com.br/maps/dir/-22.817303,-47.069732/-23.555728,-46.662584/-23.555728,-46.662584/-21.18118,-47.791368/-22.986072,-43.210891/-19.810498,-43.977416/-18.872015,-41.957341/-20.361883,-40.299458/@-21.5437532,-47.4932151,6.25z\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"#@title <font color='red'> SHOW MAP {vertical-output: true}\n",
"%%html\n",
"<iframe style=\"height: 500px; width: 100%; border: none;\" src=\"https://facilmap.org/mymap?search=brazil&amp;toolbox=true;interactive=false\"></iframe>"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 521
},
"cellView": "form",
"id": "R5NLCnJopTOZ",
"outputId": "265813a0-1eb3-4d0b-f4da-2d5217cb6821"
},
"execution_count": 141,
"outputs": [
{
"output_type": "display_data",
"data": {
"text/html": [
"<iframe style=\"height: 500px; width: 100%; border: none;\" src=\"https://facilmap.org/mymap?search=brazil&amp;toolbox=true;interactive=false\"></iframe>"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {}
}
]
},
{
"cell_type": "markdown",
"source": [
"# **Dijkstra Algorithm**"
],
"metadata": {
"id": "QZF_8PMAeyPJ"
}
},
{
"cell_type": "code",
"source": [
"#@title <font color='red'> CUSTOM GPS VARIABLES {vertical-output: true}\n",
"\n",
"Number_of_Variables = 9 #@param {type:\"slider\", min:1, max:10, step:1}\n",
"\n",
"\n",
"GPS_1,A1 = -25.470538, -49.265299 #@param {type:\"raw\"}\n",
"GPS_2,A2 = -25.069671, -50.164804 #@param {type:\"raw\"}\n",
"GPS_3,A3 = -23.286567, -51.178127 #@param {type:\"raw\"}\n",
"GPS_4,A4 = -23.419820, -51.940818 #@param {type:\"raw\"}\n",
"GPS_5,A5 = -23.549300, -51.456034 #@param {type:\"raw\"}\n",
"GPS_6,A6 = -25.403297, -51.491502 #@param {type:\"raw\"}\n",
"GPS_7,A7 = -24.953373, -53.450593 #@param {type:\"raw\"}\n",
"GPS_8,A8 = -23.753024, -53.310948 #@param {type:\"raw\"}\n",
"GPS_9,A9 = -23.067313, -52.467429 #@param {type:\"raw\"}\n",
"GPS_10,A10 = 0,0#@param {type:\"raw\"}\n",
"\n",
"\n",
"VARs = [[GPS_1,A1],[GPS_2,A2],[GPS_3,A3],[GPS_4,A4],[GPS_5,A5],[GPS_6,A6],[GPS_7,A7],[GPS_8,A8],[GPS_9,A9],[GPS_10,A10]]\n",
"GPS = []\n",
"loop = 0\n",
"\n",
"for i in VARs:\n",
" if loop < Number_of_Variables:\n",
" GPS.append(i)\n",
" \n",
" if loop == Number_of_Variables:\n",
" break\n",
"\n",
" loop = loop + 1\n",
"\n",
"print(\"GPS VARIABLES:\", *GPS,sep='\\n')"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"cellView": "form",
"id": "MiMnWexNdGZQ",
"outputId": "1ab18666-2fa2-4124-cb4b-5a5c54f7bcab"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"GPS VARIABLES:\n",
"[-25.470538, -49.265299]\n",
"[-25.069671, -50.164804]\n",
"[-23.286567, -51.178127]\n",
"[-23.41982, -51.940818]\n",
"[-23.5493, -51.456034]\n",
"[-25.403297, -51.491502]\n",
"[-24.953373, -53.450593]\n",
"[-23.753024, -53.310948]\n",
"[-23.067313, -52.467429]\n"
]
}
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "6pWoZGsDH2oq",
"outputId": "dbb126d6-d02e-4870-bad1-bd76935160f6",
"cellView": "form"
},
"source": [
"#@title <font color='red'> GET SHORTEST PATH ACCORDING TO GPS LOCATIONS {vertical-output: true}\n",
"\n",
"from collections import defaultdict\n",
"from math import sqrt\n",
"\n",
"# Shortest path to all coordinates from any node\n",
"# Coordinates must be provided as a list containing lists of\n",
"# x/y pairs. ie [[23.2321, 58.3123], [x.xxx, y.yyy]]\n",
"\n",
"\n",
"def distance_between_coords(x1, y1, x2, y2):\n",
" #x1,x2,y1,y2 = int(x1),int(x2),int(y1),int(y2),\n",
" distance = sqrt(((x2 - x1) ** 2) + ((y2 - y1) ** 2))\n",
" return distance\n",
"\n",
"\n",
"# Adds \"names\" to coordinates to use as keys for edge detection\n",
"def name_coords(coords):\n",
" coord_count = 0\n",
" for coord in coords:\n",
" coord_count += 1\n",
" coord.append(coord_count)\n",
" return coords\n",
"\n",
"\n",
"# Creates a weighted and undirected graph\n",
"# Returns named coordinates and their connected edges as a dictonary\n",
"def graph(coords):\n",
" coords = name_coords(coords)\n",
" graph = defaultdict(list)\n",
" edges = {}\n",
" for current in coords:\n",
" for comparer in coords:\n",
" if comparer == current:\n",
" continue\n",
" else:\n",
" weight = distance_between_coords(current[0], current[1],\n",
" comparer[0], comparer[1])\n",
" graph[current[2]].append(comparer[2])\n",
" edges[current[2], comparer[2]] = weight\n",
" return coords, edges\n",
"\n",
"\n",
"# Returns a path to all nodes with least weight as a list of names\n",
"# from a specific node\n",
"def shortest_path(node_list, edges, start):\n",
" neighbor = 0\n",
" unvisited = []\n",
" visited = []\n",
" total_weight = 0\n",
" current_node = start\n",
" for node in node_list:\n",
" if node[2] == start:\n",
" visited.append(start)\n",
" else:\n",
" unvisited.append(node[2])\n",
" while unvisited:\n",
" for index, neighbor in enumerate(unvisited):\n",
" if index == 0:\n",
" current_weight = edges[start, neighbor]\n",
" current_node = neighbor\n",
" elif edges[start, neighbor] < current_weight:\n",
" current_weight = edges[start, neighbor]\n",
" current_node = neighbor\n",
" total_weight += current_weight\n",
" unvisited.remove(current_node)\n",
" visited.append(current_node)\n",
" return visited, total_weight\n",
"\n",
"coords = GPS\n",
"coords, edges = graph(coords)\n",
"shortest_path(coords, edges, 3)\n",
"shortest_path_taken = []\n",
"shortest_path_weight = 0\n",
"\n",
"for index, node in enumerate(coords):\n",
" path, weight = shortest_path(coords, edges, index + 1)\n",
" print('--------------------------------------')\n",
" print(\"Path\", index + 1, \"=\", path)\n",
" print(\"Weight =\", weight)\n",
" if index == 0:\n",
" shortest_path_weight = weight\n",
" shortest_path_taken = path\n",
" elif weight < shortest_path_weight:\n",
" shortest_path_weight = weight\n",
" shortest_path_taken = path\n",
"print('--------------------------------------')\n",
"print(\"The shortest path to all nodes is:\", shortest_path_taken)\n",
"print(\"The weight of the path is:\", shortest_path_weight)\n",
"print(\"\")"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"--------------------------------------\n",
"Path 1 = [1, 2, 6, 3, 5, 4, 9, 7, 8]\n",
"Weight = 25.015979046405008\n",
"--------------------------------------\n",
"Path 2 = [2, 1, 6, 5, 3, 4, 9, 7, 8]\n",
"Weight = 18.572364899232838\n",
"--------------------------------------\n",
"Path 3 = [3, 5, 4, 9, 2, 6, 8, 7, 1]\n",
"Weight = 14.559882453612202\n",
"--------------------------------------\n",
"Path 4 = [4, 5, 9, 3, 8, 6, 7, 2, 1]\n",
"Weight = 13.300669901243038\n",
"--------------------------------------\n",
"Path 5 = [5, 3, 4, 9, 6, 8, 2, 7, 1]\n",
"Weight = 13.072727024542393\n",
"--------------------------------------\n",
"Path 6 = [6, 2, 5, 7, 4, 3, 1, 8, 9]\n",
"Weight = 16.621210214168105\n",
"--------------------------------------\n",
"Path 7 = [7, 8, 6, 9, 4, 5, 3, 2, 1]\n",
"Weight = 20.259876766942337\n",
"--------------------------------------\n",
"Path 8 = [8, 9, 7, 4, 5, 3, 6, 2, 1]\n",
"Weight = 18.01692310571069\n",
"--------------------------------------\n",
"Path 9 = [9, 4, 8, 5, 3, 7, 6, 2, 1]\n",
"Weight = 15.862656511332144\n",
"--------------------------------------\n",
"The shortest path to all nodes is: [5, 3, 4, 9, 6, 8, 2, 7, 1]\n",
"The weight of the path is: 13.072727024542393\n",
"\n"
]
}
]
},
{
"cell_type": "code",
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "aZg70DeFr55o",
"outputId": "0c4b6a0c-c747-445b-c329-d557c3cecc58",
"cellView": "form"
},
"source": [
"#@title <font color='red'> GENERATE ROUTE LINK ON OSRM GOOGLE MAPS {vertical-output: true}\n",
"\n",
"\n",
"link = [\"www.google.com.br/maps/dir/\"]\n",
"\n",
"VARs = [[GPS_1,A1],[GPS_2,A2],[GPS_3,A3],[GPS_4,A4],[GPS_5,A5],[GPS_6,A6],[GPS_7,A7],[GPS_8,A8],[GPS_9,A9],[GPS_10,A10]]\n",
"GPS = []\n",
"loop = 0\n",
"\n",
"#Upgrade variables\n",
"for i in VARs:\n",
" if loop < Number_of_Variables:\n",
" GPS.append(i)\n",
" \n",
" if loop == Number_of_Variables:\n",
" break\n",
"\n",
" loop = loop + 1\n",
"\n",
"# Function to convert list to string \n",
"def listToString(s): \n",
" str1 = \"\" \n",
" for ele in s: \n",
" str1 += ele \n",
" return str1 \n",
"\n",
"print(shortest_path_taken)\n",
"# Loop to add gps coords\n",
"for i in shortest_path_taken:\n",
" i -= 1\n",
" gps_value = str(GPS[i])+\"/\"\n",
" link.append(gps_value)\n",
" print(gps_value)\n",
"\n",
"# Final links and remove characters\n",
"final_link = listToString(link)\n",
"remove = [\"[\", \" \", \"]\"]\n",
"for i in remove:\n",
" final_link = final_link.replace(i,\"\")\n",
" \n",
"print(final_link)\n"
],
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[5, 3, 4, 9, 6, 8, 2, 7, 1]\n",
"[-23.5493, -51.456034]/\n",
"[-23.286567, -51.178127]/\n",
"[-23.41982, -51.940818]/\n",
"[-23.067313, -52.467429]/\n",
"[-25.403297, -51.491502]/\n",
"[-23.753024, -53.310948]/\n",
"[-25.069671, -50.164804]/\n",
"[-24.953373, -53.450593]/\n",
"[-25.470538, -49.265299]/\n",
"www.google.com.br/maps/dir/-23.5493,-51.456034/-23.286567,-51.178127/-23.41982,-51.940818/-23.067313,-52.467429/-25.403297,-51.491502/-23.753024,-53.310948/-25.069671,-50.164804/-24.953373,-53.450593/-25.470538,-49.265299/\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"#@title <font color='red'> GENERATE ROUTE LINK ON OSRM {vertical-output: true}\n",
"\n",
"\n",
"link = [\"http://map.project-osrm.org/?z=11&center=\"]\n",
"space1 = \"%2C\"\n",
"space2 = \"&loc=\"\n",
"final_link = [baselink]\n",
"\n",
"# Function to convert list to string \n",
"def listToString(s): \n",
" str1 = \"\" \n",
" for ele in s: \n",
" str1 += ele \n",
" return str1 \n",
"\n",
"print(shortest_path_taken)\n",
"# Loop to add gps coords\n",
"for i in shortest_path_taken:\n",
" i -= 1\n",
" gps_value = str(GPS[i])+\"&loc=\"\n",
" link.append(gps_value)\n",
" print(gps_value)\n",
"\n",
"# Final links and remove characters\n",
"\n",
"final_link = listToString(link)\n",
"remove = [\",\"]\n",
"for i in remove:\n",
" final_link = final_link.replace(i,\"%2C\")\n",
"\n",
"final_link = listToString(link)\n",
"remove = [\"[\", \" \", \"]\"]\n",
"for i in remove:\n",
" final_link = final_link.replace(i,\"\")\n",
"\n",
"\n",
" \n",
"print(final_link)\n",
"\n"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"cellView": "form",
"id": "koqjeLV2wYda",
"outputId": "9026d332-abc4-47a0-9d63-0417fd8fa415"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[5, 3, 4, 9, 6, 8, 2, 7, 1]\n",
"[-23.5493, -51.456034]&loc=\n",
"[-23.286567, -51.178127]&loc=\n",
"[-23.41982, -51.940818]&loc=\n",
"[-23.067313, -52.467429]&loc=\n",
"[-25.403297, -51.491502]&loc=\n",
"[-23.753024, -53.310948]&loc=\n",
"[-25.069671, -50.164804]&loc=\n",
"[-24.953373, -53.450593]&loc=\n",
"[-25.470538, -49.265299]&loc=\n",
"http://map.project-osrm.org/?z=11&center=-23.5493,-51.456034&loc=-23.286567,-51.178127&loc=-23.41982,-51.940818&loc=-23.067313,-52.467429&loc=-25.403297,-51.491502&loc=-23.753024,-53.310948&loc=-25.069671,-50.164804&loc=-24.953373,-53.450593&loc=-25.470538,-49.265299&loc=\n"
]
}
]
},
{
"cell_type": "markdown",
"source": [
"## Future Steps:\n",
"\n",
"Use [OSMR](http://project-osrm.org/) to get the lenth of the roads to each destination with an API\n",
"\n",
"See doc: http://project-osrm.org/docs/v5.24.0/api/#route-service"
],
"metadata": {
"id": "Gr33Gqyz43Lq"
}
},
{
"cell_type": "code",
"source": [
"#Example:\n",
"\n",
"!curl 'http://router.project-osrm.org/route/v1/driving/-23.5493,-51.456034;-23.286567,-51.178127;-23.41982,-51.940818?overview=false'\n"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "OJLe-5zw45DY",
"outputId": "56c093af-801a-483d-e84d-a6dd03debb06"
},
"execution_count": 146,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"{\"code\":\"Ok\",\"waypoints\":[{\"hint\":\"ofcxgaL3MYGBAAAAAAAAAEYFAAAAAAAAKomPQQAAAAASFjxDAAAAAIEAAAAAAAAARgUAAAAAAADnuwCA1y_T_WO1w_yMqpj-3tfu_AQAjwIdH2pR\",\"distance\":926472.964712,\"location\":[-36.491305,-54.282909],\"name\":\"\"},{\"hint\":\"ofcxgaL3MYGBAAAAAAAAAEYFAAAAAAAAKomPQQAAAAASFjxDAAAAAIEAAAAAAAAARgUAAAAAAADnuwCA1y_T_WO1w_zZrJz-cRXz_AQAjwIdH2pR\",\"distance\":956746.87139,\"location\":[-36.491305,-54.282909],\"name\":\"\"},{\"hint\":\"ofcxgaL3MYGBAAAAAAAAAEYFAAAAAAAAKomPQQAAAAASFjxDAAAAAIEAAAAAAAAARgUAAAAAAADnuwCA1y_T_WO1w_xUpJr-LnLn_AQAjwIdH2pR\",\"distance\":913070.807793,\"location\":[-36.491305,-54.282909],\"name\":\"\"}],\"routes\":[{\"legs\":[{\"steps\":[],\"weight\":0,\"distance\":0,\"summary\":\"\",\"duration\":0},{\"steps\":[],\"weight\":0,\"distance\":0,\"summary\":\"\",\"duration\":0}],\"weight_name\":\"routability\",\"weight\":0,\"distance\":0,\"duration\":0}]}"
]
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment