Date: Exp. No.: Page No.
Aim:
To write a program to Compare the performance of Single Source Shortest Paths
using Greedy method when the graph is represented by adjacency matrix and
adjacency lists.
Program:
import heapq
import time
import sys
def dijkstra_matrix(graph, src):
V = len(graph)
dist = [sys.maxsize] * V
dist[src] = 0
visited = [False] * V
for _ in range(V):
u = min_distance(dist, visited)
visited[u] = True
for v in range(V):
if graph[u][v] > 0 and not visited[v] and dist[u] + graph[u][v] < dist[v]:
dist[v] = dist[u] + graph[u][v]
return dist
def min_distance(dist, visited):
min_val = sys.maxsize
min_index = -1
for v in range(len(dist)):
Data Structures Laboratory
Date: Exp. No.: Page No.:
if dist[v] < min_val and not visited[v]:
min_val = dist[v]
min_index = v
return min_index
def dijkstra_list(graph, src):
V = len(graph)
dist = [sys.maxsize] * V
dist[src] = 0
pq = [(0, src)] # (distance, vertex)
while pq:
current_dist, u = heapq.heappop(pq)
if current_dist > dist[u]:
continue
for neighbor, weight in graph[u]:
distance = current_dist + weight
if distance < dist[neighbor]:
dist[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return dist
def compare_performance(V):
import random
random.seed(42)
Data Structures Laboratory
Date: Exp. No.: Page No.:
matrix = [[0 if i == j else random.randint(1, 10) if random.random() < 0.5 else 0 for j
in range(V)] for i in range(V)]
adj_list = [[] for _ in range(V)]
for i in range(V):
for j in range(V):
if matrix[i][j] != 0:
adj_list[i].append((j, matrix[i][j]))
src = 0
start = time.time()
dijkstra_matrix(matrix, src)
matrix_time = time.time() - start
start = time.time()
dijkstra_list(adj_list, src)
list_time = time.time() - start
print(f"Time taken by adjacency matrix: {matrix_time:.6f} seconds")
print(f"Time taken by adjacency list: {list_time:.6f} seconds")
compare_performance(500)
Output:
Time taken by adjacency matrix: 0.038538 seconds
Time taken by adjacency list: 0.010638 seconds
Result:
Hence the Program to compare the performance of Single Source Shortest Paths
using Greedy method
when the graph is represented by adjacency matrix and adjacency lists.
Data Structures Laboratory
Date: Exp. No.: Page No.:
Data Structures Laboratory
