Python, использующий алгоритм Дейкстры для поиска возможных путей - PullRequest
Новая
       9

Python, использующий алгоритм Дейкстры для поиска возможных путей

1 голос
/ 06 мая 2019

У меня есть несколько точек X и Y, которые выводятся другой программой, и мне интересно, есть ли способ использовать алгоритм Дейкстры для планирования наиболее вероятного пути для соединения всех точек?

Например, 

                           ----4------5
                           |
8------7-----6----[0]------1-------2-----3
       |
    9---

Символ [0] в примере будет отправной точкой, а числа будут точками из импортированного файла.Допустим, эти точки: .. 

point    X    Y
  1      2    0
  2      4    0
  3      6    0
  0      0    0
  4      2.5  2.5
  5      4.5  2.5
  6      -2   0
  7      -4   0
  8      -6   0
  9      -4.5 -2.5

После того, как эти точки отправлены в алгоритм Дейкстры, я бы хотел, чтобы выходной путь был примерно таким ... 

output= {
            '0': ['1', '6'],
            '1': ['2', '4'],
            '2': ['3'],
            '4': ['5'],
            '6': ['7'],
            '7': ['8','9']
            }

Если вы заметилиточка 0 может быть не в самом начале данных, но может быть где-то посередине.Кроме того, вывод включает в себя все точки, ни один из них не пропущен.

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

Какой-то рабочий код 

import math, collections
data = {0.0: [0.0, 0.0], 1.0: [1.0, 0.0], 2.0: [2.0, 0.0], 3.0: [3.0, 0.0], 4.0: [1.5, 0.5], 5.0: [2.5, 0.5], 6.0: [-1.0, 0.0], 7.0: [-2.0, 0.0], 8.0: [-3.0, 0.0], 9.0: [-2.5, -0.5]}
def group(d, start, seen = []):
   x, y = d[start]
   r = [a for a, [j, k] in d.items() if a != start and a not in seen and math.hypot(abs(x-j), abs(y-k)) <= 1]
   if not r:
     return {}
   result = {start:r}
   for i in r:
     result.update(group(d, i, seen+[start, *r]))
   return result

result = group(data, 0)

Я нашел пример алгоритма Дейкстры Здесь

Алгоритм Дейкстры 

import sys

class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

    def printSolution(self, dist):
        print("Vertex tDistance from Source")
        for node in range(self.V):
            print(node, "t", dist[node])

    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):

        # Initilaize minimum distance for next node
        min = sys.maxsize

        # Search not nearest vertex not in the
        # shortest path tree
        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    # Funtion that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):

        dist = [sys.maxsize] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # u is always equal to src in first iteration
            u = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the
            # shotest path tree
            sptSet[u] = True

            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shotest path tree
            for v in range(self.V):
                if self.graph[u][v] > 0 and sptSet[v] == False and \
                dist[v] > dist[u] + self.graph[u][v]:
                        dist[v] = dist[u] + self.graph[u][v]

        self.printSolution(dist)

# Driver program
g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
           [4, 0, 8, 0, 0, 0, 0, 11, 0],
           [0, 8, 0, 7, 0, 4, 0, 0, 2],
           [0, 0, 7, 0, 9, 14, 0, 0, 0],
           [0, 0, 0, 9, 0, 10, 0, 0, 0],
           [0, 0, 4, 14, 10, 0, 2, 0, 0],
           [0, 0, 0, 0, 0, 2, 0, 1, 6],
           [8, 11, 0, 0, 0, 0, 1, 0, 7],
           [0, 0, 2, 0, 0, 0, 6, 7, 0]
          ];

g.dijkstra(0);
# This code is contributed by Divyanshu Mehta
...