Mini Algorithms

Mini-Algorithms.md

Mini-Algorithms

This gist showcases two simple yet effective algorithms: the Sieve of Eratosthenes for finding prime numbers and Dijkstra's algorithm for finding the shortest path in a graph.

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. It's named after the ancient Greek mathematician Eratosthenes, who introduced this method around 240 BC. The algorithm works by iteratively marking the multiples of each prime number, starting from 2.

The time complexity of the Sieve of Eratosthenes is O(n log log n) for finding all prime numbers up to n, which makes it one of the most efficient methods for finding small to moderately large prime numbers.

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0], primes[1] = False, False

    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i*i, n + 1, i):
                primes[j] = False

    return [i for i, prime in enumerate(primes) if prime]

print(sieve_of_eratosthenes(50))

Dijkstra's Algorithm

Dijkstra's algorithm is a graph search algorithm that finds the shortest path between nodes in a weighted graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm works by maintaining a set of unvisited nodes and selecting the one with the smallest known distance from the start node, then updating the distances to its neighbors.

The time complexity of Dijkstra's algorithm depends on the data structure used for the priority queue. With a binary heap, its time complexity is O(|V|^2), where |V| is the number of vertices in the graph. However, using more advanced data structures like Fibonacci heaps can reduce the time complexity to O(|V|log|V| + |E|), where |E| is the number of edges in the graph.

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra(graph, 'A'))