Page 42 - 4336

Розв'язок.

Швидкість обороту капіталу S n-го шляху транспортного

засобу знайдемо як сумарну вигоду шляху, поділену на сумарний

b .
a /
час, тобто S n   i  i
1. a =1+6+14+8+15=44; b =2+9+4+8+9=32; S =44/32=1.375;
i
1
i
2. a =1+6+8+15+10=40; b =2+9+6+8+4=29; S =40/29=1.379;
2
i
i
3. a =10+3+6+8+15=42; b =3+2+9+6+9=29; S =42/29=1.448;
i
i
3
4. a =9+8+15+3+1=36; b =6+6+8+2+2=24; S =36/24=1.5.
i
i
4
Отже, найбільш вигідний з точки зору швидкості обороту
капіталу є четвертий шлях: AСEDBA.

4.2 Алгоритми пошуку найкоротшого шляху

Кожній дузі (v, w) вхідного графа G поставимо у

відповідність число с(v, w). Якщо в графі G відсутня деяка дуга
(v, w), покладемо с(v, w)=∞.

Для будь-яких двох вершин v та w графа G можуть існувати
кілька шляхів, що з'єднують вершину v з вершиною w.

Розглянемо алгоритм, який визначає такий шлях, що веде з

вершини v у вершину w, який має мінімально можливу довжину.

Цей шлях називається найкоротшим шляхом між вершинами v та

w. Даний алгоритм запропонований у 1959 р. видатним

нідерландським вченим в області інформатики та програмування

Едсгером Дейкстрою і дозволяє знаходити в графі найкоротший

шлях між двома виділеними вершинами v і w при позитивних

довжинах дуг. Він вважається одним з найбільш ефективних

алгоритмів розв'язку задачі.

Головна ідея, що лежить в основі алгоритму Дейкстри,

гранично проста. Припустимо, що нам відомі m вершин,

найближчих до вершини v (близькість будь-якої вершини х до

42