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.
1234567891011121314151617class 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
Tack för dina kommentarer!
single
Fråga AI
Fråga AI
Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal
Sammanfatta detta kapitel
Explain code
Explain why doesn't solve task
Awesome!
Completion rate improved to 7.69
Preparation
Svep för att visa menyn
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.
1234567891011121314151617class 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
Tack för dina kommentarer!
Awesome!
Completion rate improved to 7.69single