Алгоритмы для двунаправленных графов

Question

Скажем, у меня есть граф (сеть) узлов с весами на следующем: 1. путешествовать в одну сторону по соединению между двумя узлами. 2. путешествие другим путем по каналу между двумя узлами (они могут быть разными) 3. переход с одной ссылки на другую.

Кроме того, некоторые узлы являются односторонними.

В этом случае, какие бы лучшие алгоритмы для: а) найти минимальное остовное дерево б) нахождение кратчайшего маршрута между двумя узлами в) найти путь «коммивояжера» (т. е. самый короткий маршрут, который идет везде, с минимальным дублированием)?

Кроме того, лучше ли рассматривать двунаправленную вещь как два однонаправленных пути, а не двунаправленный путь с разными весами в каждом направлении?

--- пример ---

              3
  A --<2/3>-- B --<3/2>-- C
  | 1        2|3
  |           |
  ^1/4       ^4/3
  |           |
  |3         4|
8 D --<3/5>-- E
  |2
  |
1 ^3/1
  |
  |
  F

Где <2/3> означает вес 2 едущих влево и 3 едущих вправо. ^ 1/4 означает 1 путешествие вверх и 4 путешествие вниз. Одно число между двумя ссылками - это стоимость смены ссылок - например, переход с AD на DF стоит 8, а с AB на BE стоит 2.

Надеюсь, это имеет смысл ...

Simon

(p.s извинения за плохую терминологию - "ссылки", "края" - все, что вам нравится;))

---

Чтобы попытаться объяснить типы взвешивания лучше, представьте, что края - это железнодорожные пути, а узлы - это станции. Стоимость на границе - это время в пути на поезде между двумя станциями, а затраты на узлы - это то, как долго проходит время обмена (которое может варьироваться между краями даже в одном и том же узле, в зависимости от того, как далеко находится платформа, насколько регулярный сервис и т. д.).

Answer 1

Да, рассматривайте их как два ребра вместо одного.Тогда вы можете без проблем использовать традиционные алгоритмы теории графов, особенно если вам всегда гарантировано иметь веса в каждом направлении.Эти алгоритмы легко найти, если вы просто используете «нормальный» граф, как я только что помог вам создать.

Вы можете использовать Дейкстры для кратчайшего пути.

Вы можете Прима для минимального связующего дерева.

Вы можете использовать Google для асимметричного TSP, чтобы попытаться найти алгоритм для этого, и я уверен, что Введение в алгоритмыУ тоже есть кое-что по этому поводу.Извините, я не смог найти хорошую реализацию этого для вас.Здесь также есть пара хороших вопросов об асимметричном TSP, теперь, когда вы знаете, что он называется асимметричным TSP.

Удачи!Я люблю теорию графов.

- Брайан Дж. Стинар -

Answer 2

Для ваших «обменных» весов вы можете сделать небольшой подграф для их кодирования.Например, у вас есть:

  |   
  |3  
8 D --
  |2
  |

Вы можете закодировать это, используя только веса по краям, например:

  |
  |
  D0
  | \3
  |  \
 8|   D2--
  |  /
  | /2
  D1
  |
  |

Просто следите за тем, что вам не нужноиспользуйте край 8, чтобы перейти от D0 к D1, так как вместо этого вы можете перейти D0-> D2-> D1 для веса 5.Я не уверен, разрешено ли это в вашей первоначальной формулировке.