Вариация (сложная?) На кратчайшем пути - PullRequest
Новая
       45

Вариация (сложная?) На кратчайшем пути

0 голосов
/ 04 декабря 2011

У меня следующая проблема.Для заданного графа G = (V, E) ребро стоит cij между всеми ребрами {i, j}.У нас есть несколько источников, скажем, s1, ..., sk и одна цель, скажем, t.Проблема состоит в том, чтобы найти наименьшие совокупные затраты, идущие от s1, ... sk до t, где общее количество посещенных вершин по всем различным путям равно M. (Источники и цель не считаются посещенными вершинами и 0 <=M <= | V | -k + 1, поэтому, если M = 0, все пути идут напрямую от источника к цели.) </p>

Я придумал следующее, но пока не нашел решения.

  1. Проблема схожа с несколькими целями (t1, ..., tk) и одним источником, просто поменяв местами все ребра и сделав цели источниками и источником цели.Я подумал, что это может быть полезно, поскольку, например, Дейкстра вычисляет кратчайший путь от одного источника ко всем остальным вершинам графа.

  2. Только с одной целью и одним источником можно найти кратчайший путь с макс.количество посещенных вершин M по алгоритму Беллмана Форда.Это делается путем итеративного увеличения количества посещаемых вершин.

  3. Проблема нахождения кратчайшего пути от одного источника к одной цели при посещении вершин v1, ..., vk для малых k может быть решена следующим образом: i) вычислить кратчайший путь между всеми вершинами.II) проверить, какой из к!перестановки самые короткие.Я подумал, что это может быть полезно при преобразовании моей скорректированной задачи в 1) в проблему перехода от одного источника к одной «сверхцелевой» с обязательным посещением «старых» целей t1 = v1, ..., tk = vk.

К сожалению, объединение 1, 2 и 3 не дает решения, но может помочь.Кто-нибудь знает решение?Может ли это быть эффективно решено?

1 Ответ

1 голос
/ 05 декабря 2011

Почему бы не сделать отдельную Дейкстру для каждого с, а потом сложить затраты?

Что-то вроде: 

float totalCost;
for (int i=0; i<k; i++)
  totalCost += Dijkstra(myGraph,s[i],t);

Надеюсь, я правильно понял вопрос.

...