A graph is a set of objects called vertices that are related together with edges
ID: 3707476 • Letter: A
Question
A graph is a set of objects called vertices that are related together with edges. Not all vertices are connected to each other, e.g., in this figure you can see six vertices connected with seven edges: 6 4 1 2 So, we need to store which vertices are connected to which ones. One approach is to store the adjacency matrix. Element at i'th row and jth column of this matrix would be 1 if there is an edge between vertex i and j and 0 otherwise. For example the adjacency matrix of the above graph would be: 0 0 1 01 1 Another approach is to create an adjacency list. The ith element of this list, is a list that contains all the neighbors of vertex i. Adjacency list of the above graph would be 2 13 5 4 3 5 6 If the edges has a weight other than 1, both methods can be modified to store that as well. The containers that are defined in STL can be extremely useful to store a graph and use it in a program. One of the most famous problems in graph theory, which is also used in everyday life, is to find the shortest path between two vertices in a graph. The most efficient known solution for this problem is Dijkstra's algorithm proposed by Edsger Dijkstra in 1956. The steps of this algorithm from Wikipedia isExplanation / Answer
Following is the solution for the problem. This code takes the input and gives output as requested in the problem (It has been tested on python3)
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
def printSolution(self, dist):
print ("Vertex tDistance from Source")
for node in range(self.V):
print (node,"t",dist[node])
def minDistance(self, dist, sptSet):
min = 2**31-1
for v in range(self.V):
if dist[v] < min and sptSet[v] == False:
min = dist[v]
min_index = v
return min_index
def dijkstra(self, src):
dist = [2**31-1] * self.V
dist[src] = 0
sptSet = [False] * self.V
for cout in range(self.V):
u = self.minDistance(dist, sptSet)
sptSet[u] = True
for v in range(self.V):
if (self.graph[u][v] > 0 and sptSet[v] == False and
dist[v] > dist[u] + self.graph[u][v]):
dist[v] = dist[u] + self.graph[u][v]
return dist
print ('Enter number of cities')
n= int(input())
g = Graph(n)
print ('Enter', n,'cities')
city_hash = {}
for i in range(n):
city = input()
city_hash[city] = i
print ('Enter number of roads')
roads = int(input())
g.graph = [[0]*n for k in range(n)]
print ('Enter city pairs and distance')
for j in range(roads):
data = input().split()
a = city_hash[data[0]]
b = city_hash[data[1]]
cost = int(data[2])
g.graph[a][b] = cost
g.graph[b][a] = cost
print ('Enter source and destination (or quit)')
query = input()
if query.lower() == 'quit':
quit()
a = query.split()[0]
b = query.split()[1]
sol = g.dijkstra(city_hash[a])[city_hash[b]]
print ('shortest path length is :',sol)