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
Thanks for your feedback!
single
Ask AI
Ask AI
Ask anything or try one of the suggested questions to begin our chat
Awesome!
Completion rate improved to 7.69
Preparation
Swipe to show menu
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
Thanks for your feedback!
Awesome!
Completion rate improved to 7.69single