Page 28 - 4387

Варіант № 2

1. Використовуючи алгоритм Дейкстри, знайти у графі,

наведеному на рис. 3.3 б, найкоротший шлях між вершинами a та

g. Побудувати наростаюче орієнтоване дерево найкоротших

шляхів.

3.4 Аналіз результатів роботи. Висновки

Проаналізувавши одержані результати роботи, зробити

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

Дейкстри найкоротший шлях та його довжину.

3.5 Контрольні запитання

1. Що таке вага дуги?

2. Як визначається вага шляху?

3. Яким чином здійснюється розрахунок довжини

найкоротшого шляху між двома вершинами?

4. Чи можна алгоритм Дейкстри розглядати як процедуру

нарощування орієнтованого дерева з коренем у заданій

початковій вершині? Якщо так, то пояснити чому?

5. Чи може застосовуватись алгоритм Дейкстри до графа, у

якому дуги мають від’ємну вагу?

27