Preparation
This chapter is dedicated to different approaches to find minimum-weighted paths on graphs. We work with oriented weighted graphs here.
To solve problems, we’ll use a pre-implemented class Graph defined with an adjacency matrix, since each edge has some weight that will be stored in the matrix.
class Graph: def __init__(self, vertices=0): # init graph with this number of vertices self.g = [[0 for _ in range(vertices)] for _ in range(vertices)] def addEdge(self, u, v, w, o = False): # u - start vertex, v - end vertex, w - weight of edge, o - is it oriented self.g[u][v] = w if not o: self.g[v][u] = w def __str__(self): out = "" for row in self.g: out += str(row) + ' ' return out
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівВсе було зрозуміло?
Дякуємо за ваш відгук!
