17. Dijkstras Single Source Shortest Path Algorithm Naive implementation

Dijkstra's Algorithm¶

Single source shortest path algorithm

• Brute Force approach
• Adjacency Matrix representation

In [28]:

from utils.graph import GraphAdjMatrix as Graph

from utils.graph import GraphAdjMatrix as Graph

In [29]:

num_vertices = 9
g = Graph(num_vertices)
g.graph = [
    [0, 4, 0, 0, 0, 0, 0, 8, 0],
    [4, 0, 8, 0, 0, 0, 0, 11, 0],
    [0, 8, 0, 7, 0, 4, 0, 0, 2],
    [0, 0, 7, 0, 9, 14, 0, 0, 0],
    [0, 0, 0, 9, 0, 10, 0, 0, 0],
    [0, 0, 4, 14, 10, 0, 2, 0, 0],
    [0, 0, 0, 0, 0, 2, 0, 1, 6],
    [8, 11, 0, 0, 0, 0, 1, 0, 7],
    [0, 0, 2, 0, 0, 0, 6, 7, 0],
]

num_vertices = 9 g = Graph(num_vertices) g.graph = [ [0, 4, 0, 0, 0, 0, 0, 8, 0], [4, 0, 8, 0, 0, 0, 0, 11, 0], [0, 8, 0, 7, 0, 4, 0, 0, 2], [0, 0, 7, 0, 9, 14, 0, 0, 0], [0, 0, 0, 9, 0, 10, 0, 0, 0], [0, 0, 4, 14, 10, 0, 2, 0, 0], [0, 0, 0, 0, 0, 2, 0, 1, 6], [8, 11, 0, 0, 0, 0, 1, 0, 7], [0, 0, 2, 0, 0, 0, 6, 7, 0], ]

In [30]:

g.graph

g.graph

Out[30]:

[[0, 4, 0, 0, 0, 0, 0, 8, 0],
 [4, 0, 8, 0, 0, 0, 0, 11, 0],
 [0, 8, 0, 7, 0, 4, 0, 0, 2],
 [0, 0, 7, 0, 9, 14, 0, 0, 0],
 [0, 0, 0, 9, 0, 10, 0, 0, 0],
 [0, 0, 4, 14, 10, 0, 2, 0, 0],
 [0, 0, 0, 0, 0, 2, 0, 1, 6],
 [8, 11, 0, 0, 0, 0, 1, 0, 7],
 [0, 0, 2, 0, 0, 0, 6, 7, 0]]

In [31]:

class dijkstras_algorithm:
    def __init__(self, graph, num_vertices):
        self.graph = graph
        self.num_vertices = num_vertices
        self.dist = [float("inf")] * self.num_vertices
        self.visited = [False] * self.num_vertices

    def get_min_dist_node(self):
        min_idx = -1
        min_dist = float("inf")

        for node in range(self.num_vertices):
            if self.dist[node] < min_dist and self.visited[node] == False:
                min_dist = self.dist[node]
                min_idx = node

        return min_idx

    def dijkstras(self, src_node):

        self.dist[src_node] = 0
        for _ in range(self.num_vertices):

            u = self.get_min_dist_node()
            print(u)

            self.visited[u] = True

            for v in range(self.num_vertices):
                # if node exisits, and that node is not visited, and dist of that node is greater than
                # dist[u] + edge to v or graph[u][v]
                if (
                    self.graph[u][v] > 0
                    and self.visited[v] == False
                    and self.dist[u] + self.graph[u][v] < self.dist[v]
                ):
                    self.dist[v] = self.dist[u] + self.graph[u][v]

    def print_answer(self):
        for node in range(self.num_vertices):
            print(node, self.dist[node])

class dijkstras_algorithm: def __init__(self, graph, num_vertices): self.graph = graph self.num_vertices = num_vertices self.dist = [float("inf")] * self.num_vertices self.visited = [False] * self.num_vertices def get_min_dist_node(self): min_idx = -1 min_dist = float("inf") for node in range(self.num_vertices): if self.dist[node] < min_dist and self.visited[node] == False: min_dist = self.dist[node] min_idx = node return min_idx def dijkstras(self, src_node): self.dist[src_node] = 0 for _ in range(self.num_vertices): u = self.get_min_dist_node() print(u) self.visited[u] = True for v in range(self.num_vertices): # if node exisits, and that node is not visited, and dist of that node is greater than # dist[u] + edge to v or graph[u][v] if ( self.graph[u][v] > 0 and self.visited[v] == False and self.dist[u] + self.graph[u][v] < self.dist[v] ): self.dist[v] = self.dist[u] + self.graph[u][v] def print_answer(self): for node in range(self.num_vertices): print(node, self.dist[node])

In [32]:

obj = dijkstras_algorithm(g.graph, num_vertices=num_vertices)

obj = dijkstras_algorithm(g.graph, num_vertices=num_vertices)

In [33]:

obj.dijkstras(0)

obj.dijkstras(0)

0
1
7
6
5
2
8
3
4

In [34]:

obj.print_answer()

obj.print_answer()

0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14

In [ ]: