Dijkstra Algorithm Specific Case

Question

Я работаю над реализацией алгоритма кратчайшего пути Dijkstra в Python. График ориентирован и взвешен. График имеет 1070375 вершин. Первая задача - найти кратчайший путь между вершинами # 100562 и 1070345. Я сделал это. У меня нет проблем с этим. Но вторая задача - найти количество уникальных путей между этими вершинами, которые имеют одинаковую длину и разные внутренние вершины. Мой вопрос в том, что это означает: уникальные пути между ними, которые имеют одинаковую длину и разные внутренние вершины. Может быть несколько путей от 100562 до 1070345, или уникальный путь это также путь, например, от вершины # 111700 до вершины # 111704. Мог ли U показать это на простом графическом примере?

Answer 1

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

(111700) -2-> (1117002) -2-> (1117004) 
     \  /  / 
      \ /  3 
      1 3  /  
      \/ /  
      \/  /  
      (1117001)  

В этом случае у вас есть 2 кратчайших путей от 111700 до 1117004. Один 111700 -> 1117002 -> 1117004 длины 4, но есть еще один из 1117000 -> 1117001 -> 1117004, который также длины 4

Но 111700 -> 1117001 -> 1117002 -> 1117004, очевидно, не является кратчайшей длины пути, потому что этот путь имеет длину 5 (И заметьте, если в этом примере край 1117001 -> 1117002 был весом 1 мы имели бы третий самый короткий путь)