Похоже, я придумал свой алгоритм поиска кратчайшего пути (upd: меня опередили...)

Полностью соглашаюсь с вышесказанным. Извините, ошибся.

Действительно неориентированный граф можно представить как ориентированный циклический. Тогда проблема с топологической сортировкой вершин возникает не только в неориентированных (как я написал), но и во всех циклических графах.

Похоже, я придумал свой алгоритм поиска кратчайшего пути (upd: меня опередили...)

Недопонимание основано на том, что автор ищет путь в ориентированном графе, что является тривиальным алгоритмом. В свою очередь, алгоритмы Дейкстры и Форда-Беллмана без проблем работают на неориентированных графах.

Если рассмотреть работу данного алгоритма на неориентированном графе, то сразу возникнут проблемы:

Проблема 1. Неправильная ориентация ребра на этапе препроцессинга (этап, который автор решил опустить в посте).

Фраза "Нужно писать узлы графа в порядке их отдаленности от источника" крайне расплывчата и, если я правильно понял, может привести, например, к такому:

Дано: Неориентированный граф с 5-ю вершинами

Ребра: (1, 2), (1, 3), (2, 5), (2, 6), (3, 4), (4, 5)

Найти кратчайший путь от 1 до 6

Порядок "отдалености" от начальной вершины может быть таким, что ребра ориентируются так:

1 -> 2, 1 -> 3, 2 -> 5, 2 -> 6, 3 -> 4, 4 -> 5

Как видно, в изначальном неориентированном графе есть путь 1 -> 3 -> 4 -> 5 -> 2 -> 6. В измененном ориентированном графе такого пути нет (нет ребра 5 -> 2). Если этот путь самый короткий, то алгоритм его не найдет.

Проблема 2. Проблема возникает только если закрыть глаза на первую проблему и остальные шероховатости алгоритма, которые разобраны в других комментариях, но всё же я опишу и её.

Можно подвесить неориентированный граф за начальную вершину так, чтобы проблемы 1 не возникло. Но в таком случае алгоритм находит (не без доработок) расстояние (и путь) только от одной конкретно заданной вершины до другой конкретно заданной вершины. Напомню, что, например, Дейкстра находит от одной до всех остальных.

Дабы не быть голословным:

Дано: Неориентированный граф с 4-мя вершинами

Ребра: (1, 2), (1, 3), (2, 4), (3, 4)

Веса: (1, 2) -> 10, остальные по 1

Найти кратчайший путь от 1 до 4

Ориентируем граф: 1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4 (учли все возможные пути из вершины 1 в вершину 4)

Кратчайший путь найден: 1 -> 3 -> 4 (вес: 2)

Какой же за кратчайший путь от вершины 1 до вершины 2? Согласно алгоритму 1 -> 2 (вес: 10). Верный же ответ: 1 -> 3 -> 4 -> 2 (вес: 3)

P.S. Автору шлю лучи поддержки! Посту поставил плюс, ведь главное разобраться, а не устраивать срач.

Похоже, я придумал свой алгоритм поиска кратчайшего пути (upd: меня опередили...)

Контрпример, пользуясь терминологией автора:

graph = {
    1: {2: -4, 3: 7}
    2: {3: 10}
    3: {}
}

Проблема в том, что прибавляемая сумма зависит от длины пути.

1 -> 2 -> 3 (два ребра)

1 -> 3 (одно ребро)