Course Content

Greedy Algorithms using Python

1. Greedy Algorithms: Overview and Examples

Why Greedy?Description and Simple Example Schedule Problem Euclidean Algorithm Egyptian Fraction Problem Job Sequencing Problem

2. Greedy on Arrays

Make Arrays Equal Minimum Product Subset Jumping Frog

3. Greedy on Graphs

Preparation Dijkstra Shortest Path Algorithm Kruskal’s MST Prim's MST

Dijkstra Shortest Path Algorithm

The Dijkstra algorithm is a very popular and useful algorithm, which is used for searching the shortest path between two vertices, or between the start vertex and all other vertices at all. This algorithm isn't perfect at all, but it returns the shortest path always for a weighted graph with positive weights (or paths). Yes, sometimes edges can have a negative value of 'weight'.

This is a step-by-step algorithm to visit all the nodes, and every time update the minimum path from start to the current node. So for each vertex, we have a dist[vertex] tag – minimum path length which is found now.

Initially, the start node has tag 0 and all the other nodes have tag inf.

The algorithm is next:

Select the current vertex v. It should be the closest one (with minimum value of dist[v]) and not visited yet.
If there is no such a vertex v or the distance to it is equal to inf, we should stop the algorithm. There is no way to access the other vertices.
For each neighbor of current node v update tags: dist[neighbor] = min(dist[neighbor], dist[v] + g[v][neighbor]) - distance has the minimum value now.
Stop if all nodes are visited.

On the gif, you can see the demo of how it works. After completing the task, the graph from a gif is created, and you can follow it step-by-step.

Task

Complete the algorithm following the comments in the code.

Task

Complete the algorithm following the comments in the code.

Switch to desktop for real-world practiceContinue from where you are using one of the options below

Everything was clear?

Section 3. Chapter 2

Dijkstra Shortest Path Algorithm

Initially, the start node has tag 0 and all the other nodes have tag inf.

The algorithm is next:

Select the current vertex v. It should be the closest one (with minimum value of dist[v]) and not visited yet.
If there is no such a vertex v or the distance to it is equal to inf, we should stop the algorithm. There is no way to access the other vertices.
For each neighbor of current node v update tags: dist[neighbor] = min(dist[neighbor], dist[v] + g[v][neighbor]) - distance has the minimum value now.
Stop if all nodes are visited.

On the gif, you can see the demo of how it works. After completing the task, the graph from a gif is created, and you can follow it step-by-step.

Task

Complete the algorithm following the comments in the code.

Task

Complete the algorithm following the comments in the code.

Switch to desktop for real-world practiceContinue from where you are using one of the options below

Everything was clear?

Section 3. Chapter 2

Dijkstra Shortest Path Algorithm

Initially, the start node has tag 0 and all the other nodes have tag inf.

The algorithm is next:

Select the current vertex v. It should be the closest one (with minimum value of dist[v]) and not visited yet.
If there is no such a vertex v or the distance to it is equal to inf, we should stop the algorithm. There is no way to access the other vertices.
For each neighbor of current node v update tags: dist[neighbor] = min(dist[neighbor], dist[v] + g[v][neighbor]) - distance has the minimum value now.
Stop if all nodes are visited.

On the gif, you can see the demo of how it works. After completing the task, the graph from a gif is created, and you can follow it step-by-step.

Task

Complete the algorithm following the comments in the code.

Task

Complete the algorithm following the comments in the code.

Switch to desktop for real-world practiceContinue from where you are using one of the options below

Everything was clear?

Initially, the start node has tag 0 and all the other nodes have tag inf.

The algorithm is next:

Select the current vertex v. It should be the closest one (with minimum value of dist[v]) and not visited yet.
If there is no such a vertex v or the distance to it is equal to inf, we should stop the algorithm. There is no way to access the other vertices.
For each neighbor of current node v update tags: dist[neighbor] = min(dist[neighbor], dist[v] + g[v][neighbor]) - distance has the minimum value now.
Stop if all nodes are visited.

On the gif, you can see the demo of how it works. After completing the task, the graph from a gif is created, and you can follow it step-by-step.

Task

Complete the algorithm following the comments in the code.

Switch to desktop for real-world practiceContinue from where you are using one of the options below

Section 3. Chapter 2

Switch to desktop for real-world practiceContinue from where you are using one of the options below