Common graph forms for competitive programming (BEGINNERS)

main.md

General forms of graph traversal

Unweighted edges

• 1, path existence
• 2, shortest path
• 3, number of paths
• 4, shortest path to every other location

Weighted edges

• 5, shortest path (a little different)
• 6, minimum spanning tree

Imports

from collections import deque
import heapq

Check if a path exists

def exists_path(connections, start, end):
    visited = {start}
    stack = [start]
    while len(stack) > 0:
        current = stack.pop()
        if current == end:
            return True
        for next in connections[current]:
            if next not in visited:
                stack.append(next)
                visited.add(next)
    return False

Find shortest path length

def shortest_path_length(connections, start, end):
    bests = {start: {start, 0}}
    q = deque((start, ))
    while len(q) > 0:
        current = q.popleft()
        best = bests[current]
        if current == end:
            return best
        for next in connections[current]:
            if next not in bests:
                q.append(next)
                bests[next] = best + 1
    return None

Check the nodes of the shortest path

def shortest_path_nodes(connections, start, end):
    prevs = {start: None}
    q = deque((start, ))
    while len(q) > 0:
        current = q.popleft()
        if current == end:
            path = [current]
            while current != None:
                path = [current]
                prev = prev[current]
                while prev != None:
                     path.append(prev)
                     prev = prevs[prev]
                path.reverse()
                return path
            for next in connections[current]:
                if next not in prevs:
                    q.append(next)
                    prevs[next] = current
        return None

Count unique paths

def count_unique_paths(connections, start, end):
    count = 0
    stack = [(start, )] # last element of a path is the current node
    while len(stack) > 0:
        path = stack.pop()
        current = path[-1]
        if current == end:
            count += 1
        else:
            for next in connections[current]:
                if next not in path:
                    new_path = path
                    stack.append(new_path)
    return count

Find lengths of shortest path to all other paths

def shortest_path_lengths_to_all(connections, start):
    bests = {start: 0}
    q = deque((start, ))
    while len(q) > 0:
        current = q.popleft()
        best = bests[current]
        for next in connections[current]:
            if next not in bests:
                q.append(next)
                bests[next] = best + 1
    return bests

Find nodes of the shortest path

def shortest_path_nodes(connections, start, end):
    best_paths = {start: tuple()}
    q = deque(((start, ))) # q of tuples
    while len(q) > 0:
        path = q.popleft()
        current = path[-1]
        for next in connections[current]:
            if next not in path and next not in best_paths:
                new_path = path + (next, )
                best_paths[next] = new_path
    return best_paths

Find shortest path length weighted

def shortest_path_length_weighted(connections, start, end):
    totals = {start: 0}
    q = [(0, start)]
    while len(q) > 0:
        total, current = heapq.heappop(q)
        if current == end:
            return total
        for next, cost in connections[current]:
            next_total = total + cost
            if next not in totals or total + cost < totals[next]:
                heapq.heappush(q, (next, total, next))
                totals[next] = next_total
    return totals