Алгоритм Дейкстри: Тест

Що таке алгоритм Дейкстри?

• Алгоритм для сортування елементів

• Алгоритм для пошуку найкоротшого шляху в графі

• Алгоритм для пошуку найбільшого числа в масиві

• Алгоритм для множення матриць

Як називається вершина, яка вже була включена в шлях і не може більше бути включена в новий шлях?

• Відвідувана

• Видима

• Поточна

• Стартова

Які ваги ребер можуть бути використані в алгоритмі Дейкстри?

• Тільки довжина ребра

• Тільки час переміщення

• Тільки вартість

• Різноманітні, такі як довжина, час, вартість, паливо тощо

Яка мета алгоритму Дейкстри?

• Знайти найкоротший шлях тільки між двома вершинами

• Знайти найкоротший шлях від однієї вершини до всіх інших вершин графу

• Побудувати дерево пошуку в графі

• Визначити зв'язність графу

Що відбувається на кроці 2 алгоритму Дейкстри?

• Перевіряється, чи всі вершини графу відвідані

• Вибирається стартова вершина

• Перераховуються відстані до всіх видимих і відвіданих вершин, і якщо знаходиться менша відстань, то її замінюють

• Визначається фінішна вершина

Як в алгоритмі Дейкстри вибирається поточна вершина?

• Вибирається випадково

• Вибирається вершина, до якої відстань є найбільшою

• Вибирається вершина, до якої відстань є найменшою серед видимих вершин

• Вибирається будь-яка вершина

Яка є роль таблиць в алгоритмі Дейкстри?

• Визначають порядок відвідуваних вершин

• Зберігають відстані від стартової вершини до всіх інших вершин

• Визначають кінцевий результат

• Визначають, чи вершина видима

Чи можна використовувати алгоритм Дейкстри для орієнтованих графів?

• Так, алгоритм Дейкстри працює тільки для орієнтованих графів

• Ні, алгоритм працює тільки для неорієнтованих графів

• Так, алгоритм працює як для орієнтованих, так і для неорієнтованих графів

• Ні, алгоритм працює тільки для дерев

Який результат обчислення алгоритму Дейкстри на прикладі, коли стартова вершина - 0, а фінішна - 5, буде виглядати так: 9, 21, 11, 6, 20?

• Відстань між вершинами 0 та 5

• Мінімальні відстані з вершини 0 до всіх інших вершин

• Шлях від вершини 0 до вершини 5

• Шлях від вершини 5 до вершини 0

Як відбувається реалізація алгоритму Дейкстри в програмуванні?

• Через список суміжності з використанням словника

• Через масив суміжності

• За допомогою дерева пошуку

• Через матрицю суміжності