91 lines
2.5 KiB
Python
91 lines
2.5 KiB
Python
import heapq
|
|
|
|
class Graph:
|
|
def __init__(self):
|
|
self.graph = {} # adjacency list
|
|
self.edge_lengths = {} # edge length dictionary
|
|
|
|
def add_vertex(self, vertex):
|
|
if vertex not in self.graph:
|
|
self.graph[vertex] = []
|
|
else:
|
|
print(f"Vertex {vertex} already exists.")
|
|
|
|
def add_edge(self, vertex1, vertex2, length: float):
|
|
if vertex1 in self.graph and vertex2 in self.graph:
|
|
self.graph[vertex1].append(vertex2)
|
|
self.graph[vertex2].append(vertex1)
|
|
# Store edge length using a frozenset to avoid duplicates
|
|
self.edge_lengths[frozenset([vertex1, vertex2])] = length
|
|
else:
|
|
print("One or both vertices not found.")
|
|
|
|
def display(self):
|
|
print("Adjacency List:")
|
|
for vertex in self.graph:
|
|
print(f'{vertex}: {self.graph[vertex]}')
|
|
print("\nEdge Lengths:")
|
|
for edge, length in self.edge_lengths.items():
|
|
v1, v2 = tuple(edge)
|
|
print(f'{v1} - {v2}: {length}')
|
|
|
|
|
|
def dijkstra(self, start, end):
|
|
distances = {vertex: float('inf') for vertex in self.graph}
|
|
distances[start] = 0
|
|
previous = {vertex: None for vertex in self.graph}
|
|
queue = [(0, start)]
|
|
|
|
while queue:
|
|
current_distance, current_vertex = heapq.heappop(queue)
|
|
|
|
if current_vertex == end:
|
|
break
|
|
|
|
for neighbor in self.graph[current_vertex]:
|
|
edge = frozenset([current_vertex, neighbor])
|
|
weight = self.edge_lengths.get(edge, float('inf'))
|
|
distance = current_distance + weight
|
|
|
|
if distance < distances[neighbor]:
|
|
distances[neighbor] = distance
|
|
previous[neighbor] = current_vertex
|
|
heapq.heappush(queue, (distance, neighbor))
|
|
|
|
# Reconstruct path
|
|
path = []
|
|
current = end
|
|
while current:
|
|
path.insert(0, current)
|
|
current = previous[current]
|
|
|
|
print(f"Shortest path from {start} to {end}: {' -> '.join(path)} with length {distances[end]}")
|
|
|
|
# Example usage
|
|
g = Graph()
|
|
|
|
# City node abbreviations
|
|
A = "San Tan Valley"
|
|
B = "Phoenix"
|
|
C = "Globe"
|
|
D = "Mesa"
|
|
E = "Florence"
|
|
|
|
# Adding nodes to graph
|
|
g.add_vertex(A)
|
|
g.add_vertex(B)
|
|
g.add_vertex(C)
|
|
g.add_vertex(D)
|
|
g.add_vertex(E)
|
|
|
|
# Adding edges to graph
|
|
g.add_edge(A, B, 34)
|
|
g.add_edge(A, C, 47)
|
|
g.add_edge(B, D, 18.8)
|
|
g.add_edge(C, D, 13)
|
|
g.add_edge(B, E, 63)
|
|
|
|
g.display()
|
|
g.dijkstra(A, D)
|
|
|