ProjectAlgorithms/codes/python/DijkstraAlgo.py at main · Manali0806/ProjectAlgorithms · GitHub

History

39 lines (37 loc) · 1.69 KB

Raw

def dijkstra(current, nodes, distances):

# These are all the nodes which have not been visited yet

unvisited = {node: None for node in nodes}

# It will store the shortest distance from one node to another

visited = {}

# It will store the predecessors of the nodes

currentDistance = 0

unvisited[current] = currentDistance

# Running the loop while all the nodes have been visited

while True:

# iterating through all the unvisited node

for neighbour, distance in distances[current].items():

# Iterating through the connected nodes of current_node (for

# example, a is connected with b and c having values 10 and 3

# respectively) and the weight of the edges

if neighbour not in unvisited: continue

newDistance = currentDistance + distance

if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:

unvisited[neighbour] = newDistance

# Till now the shortest distance between the source node and target node

# has been found. Set the current node as the target node

visited[current] = currentDistance

del unvisited[current]

if not unvisited: break

candidates = [node for node in unvisited.items() if node[1]]

print(sorted(candidates, key = lambda x: x[1]))

current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]

return visited

nodes = ('A', 'B', 'C', 'D', 'E')

distances = {

'A': {'B': 5, 'C': 2},

'B': {'C': 2, 'D': 3},

'C': {'B': 3, 'D': 7},

'D': {'E': 7},

'E': {'D': 9}}

current = 'A'

print(dijkstra(current, nodes, distances))

ProjectAlgorithms/codes/python/DijkstraAlgo.py at main · Manali0806/ProjectAlgorithms · GitHub

Expand file tree

Breadcrumbs

DijkstraAlgo.py

Latest commit

History

Breadcrumbs

DijkstraAlgo.py

File metadata and controls