Алгоритм поиска кратчайшего пути

###Поиск в глубину. Используется для нахождения всех путей в графе от заданной точки. В качестве графа должен быть задан словарь. В ином случае функция не будет работать. start - это начальная точка графа, а end - конец, data - наш путь, visited - точки, которые уже посетили. В начале добавлю в data нашу стартовую точку, так как с неё начинаем движение. Рассматриваем соседи нашей точки, исключая уже посещенные. Если нашли подходящего соседа, то добавляем в data и visited, заходим рекурсивно, посещая каждого соседа данной точки. Работает с помощью метода исключения, где мы оставляем только один способ поиска пути.
def dfs(start, end, graph, data, visited):
    if len(data) == 0:
        data.append(start)
        visited.add(start)

    if start == end:
        return print(f'Путь - {data}, а количество ребер {len(data) - 1}')

    for next in set(graph[start]) - visited:
        data.append(next)
        visited.add(next)
        dfs(next, end, graph, data, visited)
        data.pop()
        visited.remove(next)

###Алгоритм Дейкстры. В качестве графа принимаем словарь, где value тоже словарь, содержащий точки, в которые можем попасть, и вес. Каждое практически действие сопровождается комментарием.
----------------------------------------------------------------
Если хотите не вручную создавать словарь словарей, то вот код.
from itertools import combinations

def matr():
    m = int(input('Введите количество вершин '))
    matr = {}
    for i, j in combinations([x for x in range(m+1)], 2):
        a = input(f'Введите расстояние между вершиной {chr(ord("A") + i)} и {chr(ord("A") + j)} (если связи нет введите {0}): ')
        if a != '0':
            try:
                matr[chr(ord("A") + i)].update({f'{chr(ord("A") + j)}': int(a)})
            except KeyError:
                matr[chr(ord("A") + i)] = {f'{chr(ord("A") + j)}': int(a)}
            try:
                matr[chr(ord("A") + j)].update({f'{chr(ord("A") + i)}': int(a)})
            except KeyError:
                matr[chr(ord("A") + j)] = {f'{chr(ord("A") + i)}': int(a)}
    return matr
-----------------------------------------------------------------------
graph = {
    'a': {'b': 5, 'c': 2},
    'b': {'a': 5, 'c': 7, 'd': 8},
    'c': {'a': 2, 'b': 7, 'd': 4, 'e': 8},
    'd': {'b': 8, 'c': 4, 'e': 6, 'f': 4},
    'e': {'c': 8, 'd': 6, 'f': 3},
    'f': {'e': 3, 'd': 4},
    }
start = input('Введите начальную точку ')
end = input('Введите конечную точку ')

def dejksra(start, end, graph):
    ### Задаем начальные переменные
    shortest_distances = {i: float('inf') for i in graph} ##самые короткие расстояния до каждой точки
    shortest_distances[start] = 0 #нет расстояния между стартом и стартом
    path = {} #самые короткий путь для каждой точки, здесь именно буква
    travel = [] #наша траектория движения.
    ###
    while len(graph) > 0:
        min_node = None #каждый раз буду заходить в новую точку, поэтому обнуляю
        for current_node in graph: #прохожусь по ключам графу
            if min_node == None:
                min_node = current_node #в первый раз у нас будет None, а дальше будет наша текущая точка
            elif shortest_distances[min_node] > shortest_distances[current_node]: #сравниваем с каждым элементом по ключу
                min_node = current_node
        for node, value in graph[min_node].items(): #раскрываем словарь внутри словаря {(b,5),(c,2)]
            if value + shortest_distances[min_node] < shortest_distances[node]: #расстояние от старта до данной точки сравниваем
                shortest_distances[node] = value + shortest_distances[min_node] #запоминаем самый короткий путь от начала до данной точки
                path[node] = min_node #запоминаем в словарь самую минимальную точку
        graph.pop(min_node) #удаляем минимальную точку, чтобы в неё не вернуться
    ###Восстановление пути из словаря. Каждый раз так возвращаем.
    while end != start:
        try:
            travel.insert(0, end)
            end = path[end]
        except:
            print('Невозможно восстановить путь.')
            break
    travel.insert(0, start)
    if shortest_distances[min_node] != float('inf'):
        return print(f'Минимальный путь - {travel}, а самая минимальная сумма - {shortest_distances[min_node]}')


dejksra(start, end, graph)

###Поиск в ширину. Для удобства можно использовать deque. Создаем словарь, где для каждой точки будет запоминаться путь от старта. Расстояние старта принимаем за 0 (расстояние от 1 до 1 == 0). Текущее число удаляем для поиска соседей с помощью словаря графа. Если мы его не проходили, то от прошлого добавляем 1. Добавляем в очередь для повторной итерации. Делается все, пока не пройдем полностью граф.

from collections import deque

def bfs(graph, root):
    distances = {}
    distances[root] = 0
    q = deque([root])
    while q:
        current = q.popleft()
        for neighbor in graph[current]:
            if neighbor not in distances:
                distances[neighbor] = distances[current] + 1
                q.append(neighbor)
    return distances

graph = {1:[2,3], 2:[1,3], 3:[1,2,4], 4:[1]}
root = 1
print(bfs(graph, root))