Онлайн-інструмент для аналізу теорії графів
Введіть ребра графа та знайдіть найкоротший шлях між вершинами. Підтримка до 1000 ребер, ваги, неорієнтовані графи. Приклад: A-B-C.
Почати роботу
Онлайн-інструмент для аналізу теорії графів
Знаходить найкоротший шлях між двома вершинами неорієнтованого графа з невід’ємними вагами за алгоритмом Дейкстри. Ребра вводяться по одному в рядку.
Приклад
A,B,2 B,C,3 A,C,10 start = A; end = C
5; A → B → C
Введення й обчислення
Введіть по одному неорієнтованому ребру в рядку: початок,кінець,вага. Приклад A,B,2; B,C,3; A,C,10 введіть у трьох окремих рядках. Десятковий роздільник ваги — крапка; коми розділяють поля.
Укажіть початкову вершину A та кінцеву C й запустіть обчислення. Очікувана відстань — 5, шлях — A → B → C.
Обмеження
Ваги мають бути невід’ємними. Межі: 1 000 ребер і 500 вершин. Алгоритм Дейкстри працює з неорієнтованими графами; центральність, компоненти зв’язності й орієнтовані шляхи не обчислюються.
Розділяйте поля комами ASCII, а дробову частину ваги — крапкою. A,B означає вагу 1; A,B, наразі читається як 0, тому вказуйте вагу явно. Порожні рядки ігноруються. Імена чутливі до регістру; прибираються лише зовнішні пробіли, коми в імені заборонені. Однаковий початок і кінець дають відстань 0 і цю вершину як шлях. Рахуються всі перелічені вершини. Суми з рухомою комою можуть округлюватися; досяжна відстань поза скінченним діапазоном спричиняє числову помилку.
Обробка виконується локально у вашому браузері.