Цел: Да се намери път между два върха v0 и v1 на неориентирано дърво G с N върха.

Идея на алгоритъма:

1. Ребрата се прочитат в списъчна структура.

2. Тръгваме от връх v0 и рекурсивно обхождаме дървото.
По време на обхождането се създава едномерен масив BT, представящ преходите в ориентирано дърво с корен v0, съответно на изходното дърво.
BT[i]=j означава, че в дървото G маршрутът от корена v0 до върха i завършва с реброто [j,i].

Забележки:

1. Не се проверява коректност на данните.

Бързодействие:

Приведеният алгоритъм има сложност O(N).

Сходни задачи и допълнителни свойства:

• всъщност алгоритъмът намира пътищата от v0 до всички останали върхове.
• идеята на алгоритъма се използва явно или неявно в много други алгоритми върху графи:
  • алгоритъмът на Дейкстра ползва подобно представяне на ориентираното дърво от оптимални пътища.
  • по-неявно, но по-буквално е използването при намиране на увеличаваща верига в задачата за най-много срещи.

ИМЕ НА ЗАДАЧАТА: treepath

ВХОДЕН ФОРМАТ:

* Ред 1: Цяло число N 
  N е броят на върховете в графа (N<=1000), 

* Редове от 2 до N: 
  Всеки ред съдържа 3 параметъра: I, J и L, които описват ребро. 
  I и J са върховете, които реброто свързва, L е дължината му.

* Ред N+1: 
  Две цяли числа v0 и v1 - начало и край на търсения маршрут.


ПРИМЕРЕН ВХОД (файл treepath.in):

6
1 2 5
1 3 4
2 4 4
2 5 3
4 6 2
1 6


ИЗХОДЕН ФОРМАТ:

* Ред 1: Дължина на пътя от v0 до v1
* Ред 2: Маршрута изписан във вида:
  v1 <-(lk)- ik ... <-(l1)- i1 <-(l0)- v0
  където i1 ... ik са междинните върхове от маршрута,
  а l0 ... lk са дължините на свързващите ги ребра.

ПРИМЕРЕН ИЗХОД:

L=11
6 <-(2)- 4 <-(4)- 2 <-(5)- 1

• програма на Pascal
• примерни входни данни