Да кажем, че имам графика (мрежа) от възли с тежести на следното: 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.
Дано има смисъл...
Саймън
(p.s. извинения за лошата терминология - "връзки", "ръбове" - както искате ;) )
За да опитате да обясните по-добре типовете претегляния, представете си, че краищата са влакови релси, а възлите са гари. Разходите на ръба са времето за пътуване с влак между две гари, а разходите на възлите са колко дълго е времето за обмен (което може да варира между ръбовете дори в един и същ възел, в зависимост от това колко далеч е платформата, колко редовна е услугата и т.н.).
