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

Question

Ниже приведен пример структуры данных я хранящийся в формате JSON:

 
{ 
    "alpha": { 
     "node1": "echo", 
     "node2": "bravo" 
    }, 
    "bravo": { 
     "node1": "alpha", 
     "node2": "bravo", 
     "node3": "charlie" 
    }, 
    "charlie": { 
     "node1": "bravo", 
     "node2": "foxtrot" 
    }, 
    "delta": { 
     "node1": "alpha", 
     "node2": "hotel" 
    }, 
    "echo": { 
     "node1": "golf", 
     "node2": "delta" 
    }, 
    "foxtrot": { 
     "node1": "echo", 
     "node2": "india", 
     "node3": "delta" 
    }, 
    "golf": { 
     "node1": "hotel", 
     "node2": "charlie" 
    }, 
    "hotel": { 
     "node1": "foxtrot", 
     "node2": "india" 
    }, 
    "india": { 
     "node1": "charlie", 
     "node2": "hotel" 
    } 
} 

Я ищу, чтобы найти кратчайший путь между любыми двумя узлами. Например, самый короткий путь от echo к hotel является: echo ->golf ->hotel

Как вы можете видеть, эти узлы перекручивание и можно пройти их без конца. Следует также отметить, что пути узлов - это один путь. Таким образом, используя тот же самый пример выше, кратчайший путь от hotel обратно echo является: hotel ->foxtrot ->echo

Есть имя структуры данных, как это? Я знаю, что циклирование нарушает правила «дерева». Будет ли это обход графика?

Answer 1

Что вы ищете - это кратчайший путь по графику. Проверьте это:

http://networkx.github.io/documentation/latest/reference/algorithms.shortest_paths.html

Answer 2

Что у вас есть это adjacency list. Несмотря на то, что чище, чтобы иметь что-то вроде этого (удаление node1, node2 сделать это простой массив):

{ 
    "alpha": [ 
     "echo", 
     "bravo" 
    ], 
    "bravo": [ 
     "alpha", 
     "bravo", 
     "charlie" 
    ], 
    ... 
    "india": [ 
     "charlie", 
     "hotel" 
    ] 
} 

Там нет веса/расстояния, приведенные так что вы можете найти кратчайший путь с BFS. Here - это реализация.