Scribd
Upload
7 views6 pages

BFS, DFS, and Dijkstra Algorithms Explained

The document provides implementations of three graph traversal algorithms: Breadth-First Search (BFS), Depth-First Search (DFS), and Dijkstra's algorithm. BFS explores nodes level by level, while DFS explores as far as possible along each branch before backtracking. Dijkstra's algorithm finds the shortest path from a starting vertex to all other vertices in a weighted graph.

Uploaded by

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

BFS, DFS, and Dijkstra Algorithms Explained

The document provides implementations of three graph traversal algorithms: Breadth-First Search (BFS), Depth-First Search (DFS), and Dijkstra's algorithm. BFS explores nodes level by level, while DFS explores as far as possible along each branch before backtracking. Dijkstra's algorithm finds the shortest path from a starting vertex to all other vertices in a weighted graph.

Uploaded by

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

BFS

graph = {
"a":["b","c"],
"b":["a","d"],
"c":["a","d"],
"d":["c","b","e"],
"e":["d"]
}
visited = []
queue = []

def bfs(visited, graph, node):


[Link](node)
[Link](node)

while queue:
s = [Link](0)
print(s, end=" ")

for next_node in graph[s]:


if next_node not in visited:
[Link](next_node)
[Link](next_node)
print("following is the BFS: ")
bfs(visited, graph, 'a')

OUTPUT

following is the BFS:


a b c d e
In [ ]:

DFS
graph = {
"a":["b","c"],
"b":["a","d"],
"c":["a","d"],
"d":["c","b","e"],
"e":["d"]
}
visited = set()
def dfs(visited, graph, node):
if node not in visited:
print(node)
[Link](node)
for next_node in graph[node]:
dfs(visited,graph,next_node)

print("following is the dfs:")


dfs(visited,graph, "a")

output

following is the dfs:


a
b
d
c
e

dijkstra
import heapq

def dijkstra(graph, start):


distances = {vertex: float('infinity') for vertex in
graph}
distances[start] = 0
priority_queue = [(0, start)]

while priority_queue:
current_distance, current_vertex =
[Link](priority_queue)

if current_distance >
distances[current_vertex]:
continue

for neighbor, weight in


graph[current_vertex].items():
distance = current_distance + weight

if distance < distances[neighbor]:


distances[neighbor]=distance
[Link](priority_queue,
(distance,neighbor))
return distances

graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}

start_vertex = 'A'
result = dijkstra(graph, start_vertex)
print(f"Shortest distance from {start_vertex}:
{result}")
output

Shortest distance from A: {'A': 0,


'B': 1, 'C': 4, 'D': inf}

You might also like