vldmrmlkv
@vldmrmlkv
Systems engineer

Как правильно реализовать алгоритм Дейкстры в Python с применением ООП?

Дано: классы Point(вершины), Link(рёбра), Graph с логикой и алгоритмом. Вопрос не совсем про алгоритм в отдельности, а про реализацию логики где вершины и рёбра это отдельные классы.

В чем вопрос? Link(ребро) хранит две вершины и вес этого ребра, а Point(вершина) хранит Link'и в которых как минимум будет эта же вершина + соседняя, и вес. Вот эта вложенность мне не нравится, но как должно быть я не знаю.
В учебниках и интернетах это реализуется словарём типа {Вершина1: [{Вершина 2:вес}, {Вершина 3:вес}] }, здесь же это нужно реализовать классами и мне не понятная эта вложенность. мне кажется лишнеи усложнением, а как должно быть не знаю, прошу более опытных подсказать как лучше? Есть ли паттерн для подобных случаев?

class Point:
    def __init__(self):
        self._links = []

    @property
    def links(self):
        return self._links


class Link:
    def __init__(self, v1: Point, v2: Point):
        self._v1 = v1
        self._v2 = v2
        self._dist = 1

    @property
    def v1(self):
        return self._v1

    @property
    def v2(self):
        return self._v2

    @property
    def dist(self):
        return self._dist


class Graph:
    def __init__(self):
        self._links = []
        self._point = []

    def add_point(self, v):
        if v not in self._point
            self._point.append(v)

    def add_link(self, link):
        if not all(_ == link for _ in self._links):
            self._links.append(link)

    def find_path(self, start_v, stop_v):
        pass # здесь должен быть алгоритм Дейкстры
  • Вопрос задан
  • 247 просмотров
Решения вопроса 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Это все ссылки. Вершина хранит ссылки на ребра, ребра хранят ссылки на вершины. Поэтому эта вложенность не страшна. Она - головная боль сборщика мусора (так называется часть менеджера памяти, которая освобождает ненужную больше память).

Я бы действительно не вводил сущность ребро. И просто в вершинах хранил список соседних вершин (оно еще называется список смежности). Так экономнее, быстрее и проще.

В вашем подходе, чтобы получить соседнюю вершину надо взять ребро и посмотреть, какая их двух вершин не та изначальная. Или можно хранить только ориентированные ребра и все неориентированные придется раздваивать.
Ответ написан
Комментировать
mayton2019
@mayton2019
Bigdata Engineer
Графы и графовые алгоритмы являются хорошим краш-тестом для memory. Очень сложно придумать оптимальную структуру для графа чтоб было и экономно и быстро искать исходящие и входящие ребра в вершину.

Есть компактные структуры из примитивов такие как матрицы смежности например. Но они могут быть плохие
в другом. Например в поиске в глубину. Насколько Алгоритм Дейкстры пригож для этих структур - никто не знает.

Я-бы предложил брать большой граф на несколько тысяч вершин и гонять его в разных структурах добиваясь
хорошего соотношения скорости к размеру потребляемой памяти.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы