Question

This is a weighted graph algorithm starting from NBA to NFL. Using "Dijkstra’s algorithm" find me a a shortest path using Python and what is the Time complexity.

MLS 20 10 20 NBA NFL 30 15

Answer 1

Djsktra's algorithm implementation in python:-

code:-

class Graph:
def __init__(self):
    self.nodes = set()
    self.edges = defaultdict(list)
    self.distances = {}

def add_node(self, value):
    self.nodes.add(value)

def add_edge(self, fromnode, tonode, distance):
    self.edges[fromnode].append(tonode)
    self.edges[tonode].append(fromnode)
    self.distances[(fromnode, tonode)] = distance

def dijsktra(graph, initial):
visited_nodes = {initial: 0}
path = {}

nodes = set(graph.nodes)

while nodes:
    minnode= None
    for node in nodes:
      if node in visited_nodes:
        if minnodeis None:
          minnode= node
        elif visited_nodes[node] < visited_nodes[min_node]:
          minnode= node

    if minnodeis None:
      break

    nodes.remove(min_node)
    current_weight = visited_nodes[min_node]

    for edge in graph.edges[min_node]:
      weight = current_weight + graph.distance[(min_node, edge)]
      if edge not in visited_nodes or weight < visited_nodes[edge]:
        visited_nodes[edge] = weight
        path[edge] = min_node

return visited_nodes, path

Analysis of djsktras algorithm:-

I S t 0 20 NBA NNFL 30 UFC 3D NBA-NFL ? Hlere we usRelaiom 30 S) 니 30 1→3 = 30