Description
An algorithm for finding the shortest paths between nodes in a graph.Steps
- Mark all nodes as unvisited
- Mark the starting node with a current distance of 0 and the rest nodes with infinity
- Set the starting node as the current node
- For the current node, analyze all of its unvisited adjacent nodes and measure their distances by adding the current distance of the current node to the weight of the edge that connects the adjacent node and current node
- Compare the measured distance with the current distance assigned to the adjacent node and make it the new current distance of the adjacent node
- Consider all of the unvisited adjacent nodes of the current node, and mark the current node as visited
- If the destination node has been marked visited then stop, an algorithm has ended. Otherwise, choose the unvisited node marked with the least distance, set it as the new current node, and repeat the process from step 4
Example
from heapq import heappop, heappush
from sys import maxsize
from typing import Dict, List, Tuple
def dijkstra_with_priority_queue(
graph_dict: Dict[int, List[Tuple[int, int]]],
root: int,
) -> List[int]:
graph_size = len(graph_dict)
visited = [False] * graph_size
dist = [maxsize] * graph_size
dist[root] = 0
p_que = [(0, root)]
while p_que:
_, node = heappop(p_que)
if visited[node]:
continue
visited[node] = True
for adj, a_dist in graph_dict[node]:
if dist[node] + a_dist < dist[adj]:
dist[adj] = dist[node] + a_dist
heappush(p_que, (dist[adj], adj))
return dist
if __name__ == "__main__":
# node: [(adjacent node, distance)]
graph = {
0: [(1, 1)],
1: [(0, 1), (2, 3), (3, 3)],
2: [(1, 3), (3, 1), (4, 5)],
3: [(1, 3), (2, 1), (4, 1)],
4: [(2, 5), (3, 1)],
}
print(dijkstra_with_priority_queue(graph, 2))
Description
A graph traversal and path search algorithm. It's complete, optimal, and has optimal efficiency. The only drawback is the high space complexity.Steps
- Place the starting node into OPEN and find its f(n) value
- Remove the node from OPEN with the smallest f(n) value. If it is a goal node, then stop and return the path from the start to the end node.
- Otherwise remove the node from OPEN, and find all its neighbors
- Find the f(n) value of all the neighbors, place them into OPEN, and place the removed node into CLOSE
- If there are no nodes in the OPEN – return, no path exists. Otherwise, repeat the process from step 2
Example
from typing import (
Dict,
List,
Optional,
Set,
Tuple,
)
HEURISTIC = {"A": 1, "B": 1, "C": 1, "D": 1}
class Graph:
def __init__(
self,
adj: Dict[str, List[Tuple[str, int]]],
):
self.adj_list = adj
def adjacent(
self, node: str
) -> List[Tuple[str, int]]:
return self.adj_list[node]
def a_star_algorithm(
self, start: str, stop: str
) -> Optional[List[str]]:
opn_ls: Set[str] = {start}
cls_ls: Set[str] = set()
g_cost: Dict[str, int] = {start: 0}
adj: Dict[str, str] = {start: start}
while opn_ls:
node = self.lowest_cost_node(
opn_ls, g_cost
)
if not node:
print("Path does not exist!")
return None
if node == stop:
path = self.create_path(
start, node, adj
)
print(f"Path found: {path}")
return path
self.process_node(
node, opn_ls, cls_ls, g_cost, adj
)
opn_ls.remove(node)
cls_ls.add(node)
print("Path does not exist!")
return None
def lowest_cost_node(
self,
o_lst: Set[str],
g_cost: Dict[str, int],
) -> Optional[str]:
node = None
for cur in o_lst:
f_cost = self.f_cost(cur, g_cost)
if not node or f_cost int:
return g_cost[node] + self.h_cost(node)
def process_node(
self,
node: str,
o_lst: Set[str],
c_lst: Set[str],
dist: Dict[str, int],
adj_map: Dict[str, str],
) -> None:
for adj, weight in self.adjacent(node):
if (
adj not in o_lst
and adj not in c_lst
):
o_lst.add(adj)
adj_map[adj] = node
dist[adj] = dist[node] + weight
elif dist[adj] > dist[node] + weight:
dist[adj] = dist[node] + weight
adj_map[adj] = node
if adj in c_lst:
c_lst.remove(adj)
o_lst.add(adj)
@staticmethod
def h_cost(node: str) -> int:
return HEURISTIC[node]
@staticmethod
def create_path(
start: str,
node: str,
adj_map: Dict[str, str],
) -> List[str]:
path = []
while adj_map[node] != node:
path.append(node)
node = adj_map[node]
path.append(start)
path.reverse()
return path
if __name__ == "__main__":
# node: [(adjacent node, distance)]
adjacent_list = {
"A": [("B", 1), ("C", 3), ("D", 7)],
"B": [("D", 5)],
"C": [("D", 12)],
}
graph = Graph(adjacent_list)
graph.a_star_algorithm("A", "D")
Description
An efficient, general-purpose, and comparison-based sorting algorithm.Steps
- Create two variables “start” and “end”, storing the starting and end index respectively
- Find the middle of the list by using the formula as (start+end)/2 and store the result in variable mid, then divide the list into 2 sub-lists: start to mid as one sub-list and mid+1 to end as another sub-list
- Divide the sub-lists into further sub-lists by following the process in step 2
- Merge all sub-lists in sorted order to get the final list that will be in sorted order
Example
from typing import List
def merge(
left: List[int], right: List[int]
) -> List[int]:
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] List[int]:
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)
if __name__ == "__main__":
unsorted_list = [30, 51, 8, 36, 7, 5, 45, 5]
print(merge_sort(unsorted_list))
Description
An in-place sorting algorithm.Steps
- Pick the "pivot"
- Rearrange the array elements so that all values lesser than the pivot should come before the pivot and all the values greater than the pivot should come after it
- Do the above process recursively to all the sub-arrays and sort the elements
Example
from typing import List
def quick_sort(array: List[int]) -> List[int]:
if len(array) < 2:
return array
pivot = array[0]
less = [i for i in array[1:] if i pivot]
return (
quick_sort(less)
+ [pivot]
+ quick_sort(greater)
)
if __name__ == "__main__":
unsorted_list = [30, 51, 8, 36, 7, 5, 45, 5]
print(quick_sort(unsorted_list))
Description
An algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (arbitrary node for a graph) and explores as far as possible along each branch before backtracking.Steps
- Visit the root node and the adjacent unvisited vertex. Then, mark or label it as visited
- Push it inside a stack
- In case no adjacent vertex is found, perform the pop operation of the vertex from the stack
- Repeat steps 1 and 2 until all the nodes are visited and the stack is empty
- Return visited nodes
Example
from typing import Dict, List, Set
def dfs(
graph_dict: Dict[str, Set[str]], start: str
) -> List[str]:
visited = []
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.append(vertex)
stack.extend(
graph_dict[vertex] - set(visited)
)
return visited
if __name__ == "__main__":
graph = {
"A": {"B", "C"},
"B": {"A", "D", "E"},
"C": {"A", "F"},
"D": {"B"},
"E": {"B", "F"},
"F": {"C", "E"},
}
print(dfs(graph, "A"))
Description
An algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.Steps
- Take an empty queue
- Select a starting point or root node to start with and insert the data from the node into the queue
- If the queue is not empty, then we extract the node from the neighboring nodes in a breadth-wise fashion and insert its child nodes into the queue
- Return extracted nodes
Example
from typing import Dict, List, Set
def bfs(
graph_dict: Dict[str, Set[str]], start: str
) -> List:
visited = []
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
queue.extend(graph_dict[node])
return visited
if __name__ == "__main__":
graph = {
"A": {"B", "C"},
"B": {"A", "D", "E"},
"C": {"A", "F"},
"D": {"B"},
"E": {"B", "F"},
"F": {"C", "E"},
}
print(bfs(graph, "A"))
Description
An algorithm that finds a position of a target value within a sorted array.[Steps
- Begin with the mid element of the whole array as a search key
- If the value of the search key is equal to the item then return an index of the search key
- Or if the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half
- Otherwise, narrow it to the upper half
- Repeatedly check from the second point until the value is found or the interval is empty
Example
from typing import List
def binary_search(
array: List[int], x: int
) -> int:
low = 0
high = len(array) - 1
while low <= high:
mid = (low + high) // 2
if array[mid] == x:
return mid
elif array[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
if __name__ == "__main__":
test_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(binary_search(test_array, 5))
Description
An algorithm that finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree.Steps
- Sort edges of the given graph G (V, E) in non-decreasing order as per their edge weight
- Choose the smallest weighted edge from the graph and check if it forms a cycle with the spanning tree formed so far
- If there is no cycle, include this edge to the spanning tree else discard it
- Repeat steps 2 and 3 until (V - 1) number of edges are left in the spanning tree
Example
from typing import List, Tuple
def kruskal(
edges: List[Tuple[int, int, int]],
vertices: int,
) -> List[Tuple[int, int, int]]:
edges.sort(key=lambda x: x[2])
parent = list(range(vertices))
rank = [0 for _ in range(vertices)]
mst = []
for edge in edges:
u, v, _ = edge
if find(parent, u) != find(parent, v):
mst.append(edge)
union(parent, rank, u, v)
return mst
def find(pt: List[int], i: int) -> int:
return i if pt[i] == i else find(pt, pt[i])
def union(
parent: List[int],
rank: List[int],
u: int,
v: int,
) -> None:
u_root = find(parent, u)
v_root = find(parent, v)
if rank[u_root] > rank[v_root]:
parent[v_root] = u_root
elif rank[u_root] < rank[v_root]:
parent[u_root] = v_root
else:
parent[u_root] = v_root
rank[v_root] += 1
if __name__ == "__main__":
vertices_count = 4
graph_edges = [
(0, 1, 9),
(1, 2, 6),
(0, 3, 5),
(1, 3, 15),
(2, 3, 4),
]
print(kruskal(graph_edges, vertices_count))
Description
An efficient method for computing the greatest common divisor of two integers, the largest number that divides them both without a remainder.Steps
- If one of the given numbers is zero return the other as GCD
- Otherwise get number B and a reminder from the A/B division and plug them in as new numbers to the first step
Example
def gcd(a: int, b: int) -> int:
return a if b == 0 else gcd(b, a % b)
if __name__ == "__main__":
print(gcd(10, 225))
Description
An ancient algorithm for finding all prime numbers up to any given limit.Steps
- List all consecutive numbers from 2 to n
- Assign the first prime number letter p
- Beginning with p^2, perform the multiplication of incremental of p and mark the integers equal or greater than p^2 in the algorithm. These integers will be p(p + 1), p(p + 2), p(p + 3), p(p + 4) …
- Get the first unmarked number greater than p from the list and repeat step 3
- When the square of the number being tested exceeds the last number on the list. All numbers in the list left unmarked when the algorithm ends are prime numbers
Example
from typing import List
def prime_numbers(numbers: int) -> List[int]:
primes = []
sieve = [True] * (numbers + 1)
for p in range(2, numbers + 1):
if sieve[p]:
primes.append(p)
for i in range(p, numbers + 1, p):
sieve[i] = False
return primes
if __name__ == "__main__":
print(prime_numbers(100))
Description
A broad class of computational algorithms that rely on repeated random sampling to obtain numerical results.Steps
- Define a domain of possible inputs
- Generate inputs randomly from a probability distribution over the domain
- Perform a deterministic computation on the inputs
- Aggregate the results
Example
from typing import Callable, Tuple
import matplotlib.pyplot as plt
import numpy as np
from numpy import ndarray
def integral_from_a_to_b(
f: Callable[[ndarray], ndarray],
a: float,
b: float,
samples: int,
) -> Tuple[ndarray, ndarray]:
x = np.random.uniform(a, b, samples)
y = np.random.uniform(0, f(x).max(), samples)
return x, y
def fun(x: ndarray) -> ndarray:
return np.sin(x)
def main():
a = 0
b = np.pi
samples = 10000
x, y = integral_from_a_to_b(
fun, a, b, samples
)
plt.scatter(x, y, s=1)
plt.plot(x, fun(x))
plt.show()
if __name__ == "__main__":
main()
Description
An algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Steps depend on the given algorithm, but generally:Steps
- Split the input into two halves and take the respective FFTs
- Calculate the global FFT by combining the coefficients in pairs
Example
from math import cos, exp, pi, sin
from typing import List
def fft(x: List[complex]) -> List[complex]:
n = len(x)
if n == 1:
return x
even = fft(x[::2])
odd = fft(x[1::2])
return [
even[k] + e(k, n, odd)
for k in range(n // 2)
] + [
even[k] - e(k, n, odd)
for k in range(n // 2)
]
def e(k, n, odd) -> complex:
return complex_exp(-2j * pi * k / n) * odd[k]
def complex_exp(z: complex) -> complex:
return exp(z.real) * (
cos(z.imag) + 1j * sin(z.imag)
)
if __name__ == "__main__":
data = [
1.0 + 0.0j,
1.0 + 0.0j,
1.0 + 0.0j,
1.0 + 0.0j,
0.0 + 0.0j,
0.0 + 0.0j,
0.0 + 0.0j,
0.0 + 0.0j,
]
print(fft(data))
For more see: 40 Algorithms Every Programmer Should Know