Ниже — разбор вашего фрагмента, выявленные ошибки/недочёты, оценка сложности и рабочая реализация алгоритма Дейкстры (в двух вариантах: простой O(V^2) и эффективный с кучей O((V+E) log V)).

1) Что не так в исходном коде

Инициализация dist только для стартовой вершины:
dist = {s:0} — это нормально, но затем вы используете dist.get(..., inf) при выборе u. Однако итоговый словарь dist не будет содержать всех вершин (у unreachable — ключа нет), лучше сразу инициализировать dist для всех вершин значением inf.Выбор следующей вершины u:
u = min((v for v in graph if v not in visited), key=lambda x: dist.get(x, float('inf')))
Это работает, однако если все оставшиеся вершины недостижимы (их dist == inf), вы всё равно выберете какую‑то из них и далее будете «раскладывать» её соседей без смысла. Нужно прервать цикл, если минимальное расстояние == inf.Добавление в visited:
В исходном тексте видна потенциальная ошибка с отступами: если visited.add(u) случайно внутри цикла for v,w in graph[u], то вершина будет помечена посещённой слишком рано (после обработки первого соседа). Правильное место — после обработки всех соседей.Отсутствие проверки на отрицательные веса:
Дейкстра корректен только для неотрицательных весов. Надо проверять или документировать требование.Возвращаемое значение:
Возвращать dist, в котором отсутствуют недостижимые вершины, не очень удобно. Лучше вернуть словарь, где для всех вершин указано расстояние (inf для недостижимых).Эффективность:
Поиском минимальной непомеченной вершины через min вы делаете O(V) на итерацию — итого O(V^2 + E) (часто сводят к O(V^2)). Для больших разреженных графов лучше использовать приоритетную очередь (heap).

2) Временная сложность

Вариант с линейным поиском минимума (как в вашем коде): O(V^2 + E) ≈ O(V^2) в худшем случае.Вариант с кучей (heapq): O((V + E) log V) — обычно лучше для разреженных графов (E << V^2).

3) Исправленный код

a) Простой (O(V^2)), аккуратный и понятный:

import math
def dijkstra_dense(graph, s):
# graph: dict: vertex -> list of (neighbor, weight)
# вес должен быть неотрицательным
V = list(graph.keys())
dist = {v: math.inf for v in V}
dist[s] = 0
visited = set()
while len(visited) < len(V):
# выбираем непосещённую вершину с минимальным dist
u = min((v for v in V if v not in visited), key=lambda x: dist[x])
if dist[u] == math.inf:
# все оставшиеся вершины недостижимы
break
for v, w in graph.get(u, ()):
if w < 0:
raise ValueError("Dijkstra не поддерживает отрицательные веса")
newd = dist[u] + w
if newd < dist[v]:
dist[v] = newd
visited.add(u)
return dist

b) Эффективный вариант с кучей (рекомендую для большинства задач):

import heapq
import math
def dijkstra(graph, s):
# graph: dict: vertex -> list of (neighbor, weight)
# Возвращает словарь dist: vertex -> distance (math.inf, если недостижима).
# Проверка отрицательных весов не делается ради скорости; можно добавить при необходимости.
dist = {v: math.inf for v in graph}
dist[s] = 0
heap = [(0, s)]
visited = set() # опционально: можно не использовать, но помогает игнорировать повторные обработки
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
# устаревшая запись в куче
continue
# если хотите игнорировать повторные обработки одной вершины:
if u in visited:
continue
visited.add(u)
for v, w in graph.get(u, ()):
if w < 0:
raise ValueError("Dijkstra не поддерживает отрицательные веса")
nd = d + w
if nd < dist.get(v, math.inf):
dist[v] = nd
heapq.heappush(heap, (nd, v))
# если в graph нет ключа v (v встречается как цель, но не как ключ),
# dist.get(v, inf) корректно обработает этот случай
return dist

Пример использования:

graph = {'A':[('B',1),('C',4)], 'B':[('C',2)], 'C':[]}
print(dijkstra(graph, 'A')) # -> {'A':0, 'B':1, 'C':3}

4) Дополнительные замечания и рекомендации

Граф должен содержать все вершины как ключи словаря. Если есть вершины, которые появляются только как цели (neighbors), добавьте их в graph с пустым списком перед запуском.Если веса могут быть отрицательными, используйте алгоритм Беллмана–Форда или алгоритмы для взвешенных циклов.В реализации с кучей мы не используем явное уменьшение ключа (heapq не поддерживает), вместо этого пушим новые (distance, vertex) и игнорируем устаревшие записи при pop — это стандартный прием.По памяти: обе реализации требуют O(V) для dist; heap версия требует дополнительно O(E) в худшем случае для кучи из-за потенциальных повторных записей, но на практике это нормально.

Если нужно — могу:

предоставить версию, которая автоматически добавляет в graph вершины, упомянутые только как цели;добавить проверку/игнорирование отрицательных весов;или показать модульные тесты и примеры на случайных графах.