Примеры для поиска графа с использованием scipy - PullRequest
Новая
       5

Примеры для поиска графа с использованием scipy

0 голосов
/ 31 октября 2018

Мне трудно найти учебники / примеры того, как использовать и найти путь к различным алгоритмам поиска в scipy .

Наиболее распространенным в Google является этот , где в конце примера в скобках указана ошибка. 

from scipy.sparse.csgraph import dijkstra
distances, predecessors = dijkstra(graph, indices = i1, return_predecessors = True)
path = []
i = i2

while i != i1:
   path.append(word_list[i])
   i = predecessors[i]

path.append(word_list[i1])
print path[::-1]i2]

У меня нет ввода, поэтому я не мог его воспроизвести, но я думаю, что удаление i2] работает.

Главный вопрос, который у меня есть, - это как искать график, на котором вычисляются все индексы, вместо того, чтобы давать ему indices=i1, который является необязательным параметром. Аналогично, как использовать метод Floyd-Warshall и получить путь от любого индекса i,j до любого другого индекса i,j. Часть моего замешательства заключается в отсутствии описания того, что на самом деле представляет собой матрица предшественников и как ее анализировать.

Существуют ли более подробные учебные пособия, или кто-то может привести несколько простых примеров, которые можно было бы прочесать и понять?

1 Ответ

0 голосов
/ 31 октября 2018

Я буду использовать этот неориентированный граф в качестве примера (взято из Wikipedia ) и предположим, что узлы помечены 0,1, ..., 5 вместо 1,2, ..., 6.

enter image description here

Сначала нам понадобится матрица, представляющая расстояния от узла i до j: 

import numpy as np
from scipy.sparse.csgraph import shortest_path

M = np.array([[0, 7, 9, 0, 0, 14],
              [7, 0, 9, 15, 0, 0],
              [9, 10, 0, 11, 0, 2],
              [0, 15, 11, 0, 6, 0],
              [0, 0, 0, 6, 0, 9],
              [14, 0, 2, 0, 9, 0]])

Теперь мы звоним 

D, Pr = shortest_path(M, directed=False, method='FW', return_predecessors=True)

Здесь D - матрица кратчайших расстояний, а Pr - матрица предшественников. D[i, j] дает кратчайшее расстояние от узла i до узла j, а Pr[i, j] дает индекс предыдущего узла по кратчайшему пути из точки i в точку j. Pr [i, j] = -9999, если нет пути от узла i к узлу j. С method='FW' мы выбираем алгоритм Флойда-Варшалла.

И, наконец, мы можем использовать матрицу предшественников, чтобы определить функцию для получения списка узлов от кратчайшего пути от узла i до узла j: 

def get_path(Pr, i, j):
    path = [j]
    k = j
    while Pr[i, k] != -9999:
        path.append(Pr[i, k])
        k = Pr[i, k]
    return path[::-1]

Чтобы получить кратчайший путь от узла 0 до 4 (соответственно с 1 по 5 на рисунке): 

In [16]: get_path(Pr,0,4)
Out[16]: [0, 2, 5, 4]  # in the picture: 1, 3, 6, 5

In [17]: D[0,4]
Out[17]: 20.0
...