Логистика, (из точка A точку B) Опции

[ipconnect]

Ребята, выручайте. Задача интересная, прикладная, но что-то я подвис с её решением.
Чтобы проще понять, что требуется, представьте себе, что у вас есть некая страна, в которой есть для простоты 9 городов. Каждый город для удобства обозначен уникальной цифрой от 1 до 9. Между городами есть дороги (не между всеми), которые имеют определённую протяжённость, заранее известную. По некоторым дорогам можно проехать только в одну сторону, по другим - в обе. В общем всё это вышеописанное дело можно задать вот таким двумерным массивом чисел (номер строки - точка отправления, номер столбца - точка прибытия):
00 01--02-03-04--05-06--07-08-09
01(-1)(10)(-1)(11)(15)(-1)(-1)(-1)(-1)
02(-1)(-1)(21)(-1)(12)(-1)(-1)(-1)(-1)
03(-1)(21)(-1)(-1)(-1)(-1)(-1)(-1)(-1)
04(-1)(-1)(-1)(-1)(18)(19)(-1)(-1)(-1)
05(-1)(-1)(-1)(-1)(-1)(-1)(17)(-1)(-1)
06(-1)(-1)(-1)(-1)(-1)(-1)(-1)(14)(13)
07(-1)(-1)(-1)(-1)(-1)(-1)(-1)(-1)(20)
08(-1)(-1)(-1)(-1)(-1)(-1)(-1)(-1)(16)
09(-1)(-1)(-1)(-1)(-1)(-1)(-1)(-1)(-1)
В данной табличке неотрицательные цифры - это и есть расстояния между городами (может быть и ноль), а (-1) это признак того, что между этими городами в данном направлении дорога отсутствует. К примеру, между городами 1 и 2 автомобилю необходимо проехать 10 км, между городами 1 и 3 прямой дороги нет, а между городами 2 и 3 дорога в обе стороны длиной 21 км в одну сторону. Вот такие исходные данные. А вот в чём задача, которая вызывает у меня проблему, я сейчас попробую описать. У вас есть автомобиль, который должен ехать из пункта А в пункт Б. Он перемещается по одному из возможных путей, заданных в массиве. Необходимо подсчитать все возможные длины путей из точки А в точку Б, запомнив сам путь перемещения (к примеру из точки 1 в точку 9 пути 1-2-5-7-9 или 1-4-6-8-9 и т.п.) и его длину. Дальше надо сравнить эти маршруты и найти наиболее короткий (ну, это легко). Проблема вторая если один из участков между городами упирается в город, путь из которого возможен только назад в точку отправления (участок между городами 2 и 3), необходимо учесть и этот участок возможного маршрута (т.е. нарушается логика увеличения цикла, так как надо возвращаться назад).

В итоге в данном примере возможные пути выглядят следующим образом, если пункт А - это 1, а пункт Б -9:
1-2-3-2-5-7-9 (длина пути 101 км)
1-2-5-7-9 (длина пути 59 км)
1-4-5-7-9 (длина пути 56 км)
1-4-6-8-9 (длина пути 60 км)
1-4-6-9 (длина пути 43 км)
1-5-7-9 (длина пути 52 км)
Отсюда минимальное расстояние между точками А (1) и Б (9) равняется 43 км и это расстояние соответствует маршруту 1-4-6-9... Но все эти цифры и выводы надо получить программно при том, что количество городов задаётся произвольным целым числом от 1 и до хотя бы 100 (а не 9 городов, как в данном примере). Т.е. надо сделать общий алгоритм этих вычислений. И такая печаль, что у меня ни фига не получается в связи с описанными, как для меня, проблемами. Ребята, очень прошу помощи. Там есть ещё графическое продолжение, но хотя бы эту часть. Дальше я сам.