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


Meet the Greedy Algorithms course that introduces you the Greedy paradigm, which can be used in a huge amount of problems. We’ll start with classic problems, then move to the Greedy Algorithms in arrays, and finish with the hardest part – Greedy Algorithms on graphs, such as Kruskal’s Minimum Spanning Tree and Dijkstra Shortest Path Algorithm.

That would be great if you’re already familiar with Algorithms at all and such concepts as Dynamic Programming.

The Greedy Approach is to build solutions piece by piece, always choosing the most relevant and beneficial one, to achieve the optimal solution.

There is a set of interesting and non-trivial problems on arrays that use the Greedy approach.

This chapter is dedicated to different approaches to find minimum-weighted paths on graphs. We work with oriented weighted graphs here.

Greedy Algorithms using Python

Preparation

Preparation