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

Question

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

A - B - C - D 
\ /\ 
    E - F - G 

и я хочу, кратчайший путь от A к G. Это будет либо A->B->C->G, либо A->E->F->F.

Чтобы поместить это в более конкретном плане, у меня есть

var nodes = new List<Node> 

где

class Node 
{ 
    // ... properties 

    List<Node> Neighbors; 
} 

и дал некоторые Node start, end; в nodes Я хочу, чтобы найти кратчайший путь от start к end.

Я знаю, что я мог бы использовать алгоритм Джикстры с расстоянием 1 между каждым узлом, но я считаю, что для этого случая есть лучший способ?

Answer 1

BFS обхода это самый быстрый способ, чтобы решить эту проблему, потому что это позволит решить проблему в линейное время O (M + N).

BFS является порядок обхода уровень означает, что она пересекает уровень узлов на уровне :(сначала все узлы на расстоянии 1 края перемещаются и на расстоянии 2 краев проходятся и так далее.).

Answer 2

Dijkstra с расстоянием 1 или BFS - оба могут применяться. Этими типами проблем известны эти два подхода. Я не думаю, что есть другой лучший способ.