Dijkstra

Description:

an efficient algorithm for finding the shortest path from source node to dest node in a graph. The run of the algorithm is portrayed via GUI interface that displays a minimum path from source node to destination node, and all the visited nodes

---

Main logic:

we run Dijkstra on a weighted graph, where each vertex is a "square" on the screen, an edge is a connection between two adjacent squared, and the weight is 1. as an example, consider a 3x3 pixel grid:

a graph G=<V,E>, that represents the grid, is comprised of the following edges and vertexes (starting from (0,0)):

V = ['(0,0)', '(0,1)', '(0,2)', '(1,0)', '(1,1)', '(1,2)', '(2,0)', '(2,1)', '(2,2)']

E = [('(0,0)', '(1,0)', 1), ('(0,0)', '(0,1)', 1), ('(0,1)', '(0,0)', 1),...,('(2,2)', '(2,1)', 1)]

where ('(0,0)', '(1,0)', 1), for example, means that node (0,0) is connected to node (1,0) with an edge weighing 1.

also:

• the source and destination nodes are chosen by the user (two right clicks with the mouse)
• the user can "draw" (left mouse click) on the screen pixels that represents a node that doesnt exist, and therefore the algorithm wont use in runtime (these can be thought of as barriers, and they are colored black)

---

Running the Visuals :

under Dijkstra.Main execute main()

example:

• Minimum Path
• Source Node
• Destination Node
• Blocked Nodes
• Visited Nodes

---

complexity analysis

(not rigorously):

Dijkstra:
source.set_dist_from_source(0)
Q = build_min_heap(graph)  # O(V)
while Q:  # O(V)
    u = heapq.heappop(Q)  # pops the min val (get value and remove from heap) O(logV)
    neighbors_of_u = graph.get_neighbors()[u.name]
    for v in neighbors_of_u:  # O(E)
        weight_u_v = graph.get_edge_weight(u.name, v.name)
        v_dist = v.dist_from_source
        u_dist = u.dist_from_source
        if v_dist > u_dist + weight_u_v:
            v.set_dist_from_source(u_dist + weight_u_v)
            heapq.heappush(Q, v)  # O(logV)