dijkstra-algorithm/dijkstra.py at master · xxxwarrior/dijkstra-algorithm · GitHub

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#       1     3     5
#     _____a_____c______
#    |     |     |      |
# start    | 2   | 3    fin
#    |_____b_____d______|
#       4     4      2

graph = {
    'start': {'a': 1, 'b': 4},
    'a': {'b':2, 'c': 3},
    'b': {'d': 4},
    'c': {'fin': 5},
    'd': {'c': 3, 'fin': 2},
    'fin': {}
    }

costs = {
    'a': 1,
    'b': 4,
    'c': infinity,
    'd': infinity,
    'fin': infinity
    }

parents = {
    'a': 'start',
    'b': 'start',
    'c': None,
    'd': None,
    'fin': None
    }


infinity = float("inf")
processed = ["start", ]

def search():
    node = find_lowest_cost_node(costs)
    while node is not None:
        cost = costs[node]
        neighbours = graph[node]
        for i in neighbours.keys():
            new_cost = cost + neighbours[i]
            if costs[i] > new_cost:
                costs[i] = new_cost
                parents[i] = node
        processed.append(node)
        node = find_lowest_cost_node(costs)

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

def path(start, finish): #pass the names from the graph like 'start', 'fin'
    search()
    path_ = [finish, ]
    processing = finish
    while start not in path_:
        for node, parent in parents.items():
            if node == processing:
                path_.append(parent)
                processing = parent
    return path_[::-1]