dijkstraNlogN/DijkstraNlogN.py at master · dream2333/dijkstraNlogN · 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

from math import inf
from dijkstra.command import Command
from dijkstra.undigraph import UndiGraph
import heapq


class DijkstraNlogN:

    def __init__(self):
        self.graph = UndiGraph()
        self.path = []

    def caculate_path(
        self,
        start: str = "A",
    ):
        # Using hashmap to improve addressing speed
        node_state = {}
        result_path = []
        # Using the heap to get the nearest node
        temp_heap = []
        for node_name in self.graph.nodes:
            node_state[node_name] = {"nearest": False, "dist": inf}
        # The first node is not involved in sorting and inserted directly
        heapq.heappush(temp_heap, (0, self.graph[start]))
        while len(temp_heap) > 0:
            # Select the nearest node in the path
            now_node_tuple = heapq.heappop(temp_heap)
            now_node = now_node_tuple[1]
            # If the node is duplicated, skip directly
            if node_state[now_node.name]["nearest"] == True:
                continue
            result_path.append(now_node_tuple)
            # If a node has found the shortest path, set its status to true
            node_state[now_node.name]["nearest"] = True
            now_edge = now_node_tuple[0]
            # Iterate over each neighboring node
            for neighbor in now_node.neighbors:
                next_node = neighbor[1]
                next_edge = now_edge + neighbor[0]
                # Use a min heap make sure the nearest node is always at the top of the heap
                if (
                    node_state[next_node.name]["nearest"] == False
                    and next_edge < node_state[next_node.name]["dist"]
                ):
                    node_state[next_node.name]["dist"] = next_edge
                    heapq.heappush(temp_heap, (next_edge, next_node))
        self.path = result_path
        return result_path

    # Return all nodes and their weight as a list
    def get_neighbors(self, node_names):
        return self.graph[node_names].neighbors

    # Return the LSDB as a list
    def get_LSDB(self, node_names):
        if (len(self.graph[node_names].neighbors))==0:
            return []
        return self.graph.get_all_edge()

    # Return the routing table as a list
    def get_routing_table(self, node_name):
        path = self.caculate_path(node_name)
        result = []
        for dist, destination in path[1:]:
            result.append((destination, path[1][1], dist))
        return result


def test_graph():
    # Generate test nodes
    graph = UndiGraph("X", "Y", "Z")
    graph.create_edge("X", "Z", 7)
    graph.create_edge("X", "Y", 2)
    graph.create_edge("Y", "Z", 1)
    graph.update_edge("Y", "Z", -1)
    graph.update_edge("X", "Z", 5)
    return graph


if __name__ == "__main__":
    dijk = DijkstraNlogN()
    dist = dijk.caculate_path(start="X")
    print(dist)
    neighbors = dijk.get_neighbors("X")
    print(neighbors)