blob: cc8d35f7a71243b2ce4cdcf8890f1de6f1584118 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import math
def length_haversine(p1, p2):
lat1 = p1.lat
lng1 = p1.lng
lat2 = p2.lat
lng2 = p2.lng
lat1, lng1, lat2, lng2 = map(math.radians, [lat1, lng1, lat2, lng2])
dlat = lat2 - lat1
dlng = lng2 - lng1
a = math.sin(dlat / 2) ** 2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlng / 2) ** 2
c = 2 * math.asin(math.sqrt(a))
return 6372797.560856 * c # return the distance in meters
def get_closest_node_id(nodes, source_node):
""" Search through all nodes and return the id of the node
that is closest to 'source_node'. """
min_node = None
min_value = None
for node_id, node in nodes.items():
length = length_haversine(source_node, node)
if min_node == None or length < min_value:
min_node = node_id
min_value = length
return min_node
def find_shortest_path(nodes, source_id, target_id):
""" Return the shortest path using Dijkstra's algortihm. """
return []
|
