tgoop.com/the_algorithms/4947
Create:
Last Update:
Last Update:
🚗 Как найти кратчайший маршрут с помощью Apache Spark и GraphFrames
Разбираем кейс на реальных данных из OpenStreetMap — ищем оптимальный маршрут
🔍 Что делаем
1. Загружаем граф дорог города с помощью OSMnx
2. Сохраняем вершины и ребра с координатами, скоростями и геометрией
3. Загружаем всё в Spark
4. Находим кратчайший путь с помощью GraphFrames
📍 1. Скачиваем карту и строим граф улиц
import osmnx as ox
# Загрузка данных о дорогах Москвы
G = ox.graph.graph_from_place("Moscow", network_type="drive")
# Отображение дорог на карте
moscow_gdf = ox.geocoder.geocode_to_gdf("Moscow")
fig, ax = ox.plot.plot_graph(G, show=False, close=False, bgcolor="#111111", edge_color="#ffcb00", edge_linewidth=0.3, node_size=0)
moscow_gdf.plot(ax=ax, fc="#444444", ec=None, lw=1, alpha=1, zorder=-1)
# Настройка границ карты
margin = 0.02
west, south, east, north = moscow_gdf.union_all().bounds
margin_ns = (north - south) * margin
margin_ew = (east - west) * margin
ax.set_ylim((south - margin_ns, north + margin_ns))
ax.set_xlim((west - margin_ew, east + margin_ew))
plt.show()
📁 2. Сохраняем геометрическое описание города в формате GeoJSON и данные о вершинах и рёбрах в формате CSV
with open('Moscow.geojson', 'w') as file:
file.write(moscow_gdf.to_json())
nodes = G.nodes(data=True)
with open('nodes.csv', 'a') as file:
file.write("id,lat,lonn")
for (node, data) in nodes:
file.write("%d,%f,%fn" % (node, data.get("y"), data.get("x")))
edges = G.edges(data=True)
def decode_maxspeed(maxspeed):
match maxspeed:
case str():
match maxspeed.lower():
case "ru:urban": return 60
case "ru:rural": return 90
case "ru:living_street": return 20
case "ru:motorway": return 110
case _: return int(maxspeed)
case list(): return min(list(map(decode_maxspeed, maxspeed)))
case _: return maxspeed
with open('edges.csv', 'a') as file:
file.write("src,dst,maxspeed,length,geometryn")
for (src, dst, data) in edges:
maxspeed = decode_maxspeed(data.get("maxspeed", 999))
length = float(data.get("length"))
geometry = shapely.wkt.dumps(data.get("geometry"))
file.write("%d,%d,%d,%f,%sn" % (src, dst, maxspeed, length, geometry))3. Используем библиотеку GraphFrames для обработки графов на Apache Spark
from pyspark.sql import SparkSession
spark = SparkSession.builder
.config("spark.jars.packages", "graphframes:graphframes:0.8.4-spark3.5-s_2.12")
.master("local[*]")
.appName("GraphFrames")
.getOrCreate()
nodes = spark.read.options(header=True).csv("nodes.csv")
edges = spark.read.options(header=True).csv("edges.csv")
# Вычисление времени прохождения рёбер
edgesT = edges.withColumn("time", edges["length"] / edges["maxspeed"])
# Построение графа
from graphframes import *
g = GraphFrame(nodes, edgesT)
🧭 4. Ищем кратчайший путь по времени
например, от Измайлово до ЖК Зиларт
src = "257601812"
dst = "5840593081"
paths = g.shortestPaths(landmarks=[dst])
paths.filter(F.col("id") == src).show(truncate=False)
💡 Результат: 40 шагов от точки A до точки B.
Такой подход легко масштабируется на миллионы маршрутов. Используйте Spark и GraphFrames для построения логистических моделей, маршрутизации и городского планирования.
🚀 Хотите прокачаться в работе с Big Data? Изучайте Spark! Записывайтесь на курс Spark Developer от OTUS — учитесь на реальных данных и продвинутых кейсах: https://otus.pw/he60/
Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4947