Scribd
Upload
9 views2 pages

Dijkstra's Algorithm Python Implementation

The document presents a modified implementation of Dijkstra's Algorithm in Python for finding the shortest path in a graph. It includes a sample graph, execution details, and outputs the shortest path and total distance. Additionally, it analyzes the algorithm's time and space complexity, reflects on the learning experience, and discusses its real-world applications.

Uploaded by

kevinkochieng2000
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

Dijkstra's Algorithm Python Implementation

The document presents a modified implementation of Dijkstra's Algorithm in Python for finding the shortest path in a graph. It includes a sample graph, execution details, and outputs the shortest path and total distance. Additionally, it analyzes the algorithm's time and space complexity, reflects on the learning experience, and discusses its real-world applications.

Uploaded by

kevinkochieng2000
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Dijkstra’s Algorithm Assignment

Modified Python Code Implementation


import heapq

def dijkstra(graph, start, end):


queue = [(0, start, [])]
visited = set()
while queue:
(cost, current, path) = [Link](queue)
if current in visited:
continue
[Link](current)
path = path + [current]
if current == end:
return (cost, path)
for neighbor, weight in [Link](current, []):
if neighbor not in visited:
[Link](queue, (cost + weight, neighbor, path))
return float("inf"), []

# Modified Graph definition


graph = {
'A': [('B', 4), ('C', 2), ('F', 8)],
'B': [('C', 5), ('D', 10)],
'C': [('D', 3), ('E', 1)],
'D': [('E', 7), ('F', 2)],
'E': [('F', 6)],
'F': []
}

# Execution
start, end = 'A', 'F'
distance, path = dijkstra(graph, start, end)
print(f"Shortest Path: {' -> '.join(path)}")
print(f"Total Distance: {distance}")

Sample Output
Shortest Path: A -> C -> D -> F
Total Distance: 7

Analysis
Time Complexity: The time complexity of Dijkstra’s Algorithm using a priority queue is O((V + E) log
V), where V is the number of vertices and E is the number of edges. Space Complexity: The space
complexity is O(V + E) due to the adjacency list and heap used in the algorithm. Design Strategy:
Dijkstra’s Algorithm is a Greedy Algorithm that selects the unvisited node with the smallest tentative
distance. It guarantees the shortest path in graphs with non-negative edge weights.
Reflection
Working on Dijkstra’s Algorithm has enhanced my understanding of how Greedy Algorithms work in
practice. Initially, I found it challenging to see how selecting the shortest distance at each step
guarantees the overall shortest path. However, after modifying the graph and testing various cases,
the logic became clear. My “aha!” moment was realizing how the priority queue ensures we always
expand the most promising path first. This task also highlighted real-world applications, such as
GPS navigation and network routing, where efficiency matters greatly. Personally, it improved my
problem-solving approach by encouraging me to test and refine solutions instead of relying only on
theory. I feel more confident in applying algorithmic thinking to both academic work and practical
challenges in Educational Technology.

You might also like