Как я могу пройти по графику, чтобы найти кратчайший путь между источником и пунктом назначения, используя «алгоритм Дейкстры» в python? - PullRequest
Новая
       31

Как я могу пройти по графику, чтобы найти кратчайший путь между источником и пунктом назначения, используя «алгоритм Дейкстры» в python?

0 голосов
/ 23 февраля 2020

Итак, у меня есть код для реализации алгоритма Дейкстры, чтобы найти кратчайший путь во взвешенном графике от исходного узла к узлу назначения в Python 3 (python 3.8.1).

Это график, на котором я протестировал алгоритм Дейкстры, в котором я взял около 12 узлов (вершин), которые связаны между собой, и всем ребрам присвоен некоторый вес, я взял источник в качестве A и пункт назначения в качестве H.

Это вывод графика, и я могу получить из него правильный путь, но проблема в том, что я могу печатать только кратчайший путь, я не могу покажите это графически.

Это то, что я хочу решить:

Это растровое изображение, состоящее только из абсолютно белого и черного изображения, через python Я способен различать белые пиксели [0,0,0] и черные пиксели [255,255,255]. (Как показано на 3-м и 4-м фото, правый угол вниз), где бы ни находился мой курсор на графике, код может сказать (x у) пикселей, как со-о Система rdinate, а также процент RGB цвета, над которым находится курсор.

Курсор на белом цвете. (Правый угол вниз)

Если я размещу некоторые узлы на графике так же, как на упомянутом изображении, как мне применить алгоритм Дейкстры и найти кратчайший путь между синими точками (источник и пункт назначения помечены как «синие», а узлы отмечены как « красный "). Код должен быть в состоянии найти кратчайший путь только в белых пикселях, он не должен перемещаться в черных пикселях и должен выделять кратчайший путь каким-либо другим цветом, например желтым или голубым.

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

КОД: 

import itertools
import matplotlib.pyplot as plt
from scipy import ndimage
from scipy import misc
from scipy.sparse.dok import dok_matrix
from scipy.sparse.csgraph import dijkstra

# Load the image from disk as a numpy ndarray
original_img = plt.imread('map.bmp')

# Create a flat color image for graph building:
img = original_img[:, :, 0] + original_img[:, :, 1] + original_img[:, :, 2]


# Defines a translation from 2 coordinates to a single number
def to_index(y, x):
    return y * img.shape[1] + x


# Defines a reversed translation from index to 2 coordinates
def to_coordinates(index):
    return index / img.shape[1], index % img.shape[1]


# A sparse adjacency matrix.
# Two pixels are adjacent in the graph if both are painted.
adjacency = dok_matrix((img.shape[0] * img.shape[1],
                        img.shape[0] * img.shape[1]), dtype=bool)

# The following lines fills the adjacency matrix by
directions = list(itertools.product([0, 1, -1], [0, 1, -1]))
for i in range(1, img.shape[0] - 1):
    for j in range(1, img.shape[1] - 1):
        if not img[i, j]:
            continue

        for y_diff, x_diff in directions:
            if img[i + y_diff, j + x_diff]:
                adjacency[to_index(i, j),
                          to_index(i + y_diff, j + x_diff)] = True

# We chose two arbitrary points, which we know are connected
source = to_index(14, 47)
target = to_index(151, 122)

# Compute the shortest path between the source and all other points in the image
_, predecessors = dijkstra(adjacency, directed=False, indices=[source],
                           unweighted=True, return_predecessors=True)

# Constructs the path between source and target
pixel_index = target
pixels_path = []
while pixel_index != source:
    pixels_path.append(pixel_index)
    pixel_index = predecessors[0, pixel_index]


# The following code is just for debugging and it visualizes the chosen path


plt.imshow(original_img)
plt.show()

ВХОД

Это изображение, которое я использовал для ввода кода. (Он называется map.bmp и сохраняется в той же папке, что и код.)

ВЫХОД

После выполнения кода выше Я получил это как вывод.

Мне нужно разобраться, пожалуйста, помогите!

Спасибо

...