Я напишу мою проблему так:
- У меня есть ненаправленный граф с «пустыми» вершинами, но с взвешенными ребрами (назовем это расстоянием)
- Кроме того, у меня есть пары направленных "заполнений" для вершин, например, пара 1-> 2 означает от вершины, содержащей одну, до вершины, содержащей 2. 20-> 13 означает пару из 2 вершин, одна из которых заполнена числом 20, еще один с 13 .. и так далее
- Я могу размещать «заливки» вершин в любом месте графика, независимо от пары - каждое число в паре будет символизировать только 1 вершину
- Каждая вершина имеет максимум 2 исходящих / входящих ребер, но может быть пара только с одним (так, в основном, с одним)
- Там будут циклы
И я хочу создать граф с кратчайшим расстоянием между данной парой вершин.
One short and simple example
график
X---X---X
| |
X----X--+
с парами
1-> 2
1-> 3
3-> 4
2-> 5
4-> 5
will produce something like
1---2---5
| |
3----4--+
Я знаю, что это можно сделать с помощью алгоритма грубой силы и F-Warshal. Вопрос в том, если нет лучшего подхода (для 50 вершин есть 50! Комбинаций - много для расчета)
Еще раз, спасибо за ваше время, и если, еще больше за ответы :)
Хорошего дня