This page is hosted for free by zzz.com.ua, if you are owner of this page, you can remove this message and gain access to many additional features by upgrading your hosting to PRO or VIP for just 32.50 UAH.
Do you want to support owner of this site? Click here and donate to his account some amount, he will be able to use it to pay for any of our services, including removing this ad.

Шляхи між кожною парою вершин орграфа з мінімальною загальною вагою дуг

Ця сторінка призначена для студентів, що вивчають курс дискретної математики та (або) теорії графів. Безпосередньо з неї ви можете виконати своє ІДЗ, навіть якщо у вас немає на комп’ютері MATLAB. Якщо ж у вас є MATLAB, перейдіть на цю сторінку: там у вас є можливість втрутитися у сценарій (програму) обчислень. А на цій сторінці для знаходження найкоротшого шляху використовується алгоритм Флойда-Воршола (R.W.Floyd, S.A.Warshall). Докладніше див. тут, стор. 110.

Для правильної роботи з цією сторінкою ваш браузер повинен підтримувати сценарії Java Script. Увімкніть їх.

Введіть вхідні дані в області введення нижче. У першій області треба (точніше, можна) ввести координати вершин для малювання орграфа. Вони задаються у вигляді матриці n×2: у першому стовпці − x координати, у другому − y-і. Числа можна задавати цілі, з десятичною точкою або в експоненційній формі. Числа розділяйте пробілами. Загальна кількість рядків у цій області введення визначає розмір орграфа n − кількість вершин. Ці вхідні дані (координати вершин) не є обов’язковими: якщо їх не задати, то орграф буде малюватися у вигляді правильного n-кутника, а кількість вершин буде визначатися максимальним номером вершини у наступній області введення.

В наступній області введення ліва частина є обов’язковою для заповнення. В ній визначається структура орграфа. Кожна дуга в орграфі поєднує дві вершини. Номери цих вершин задаються у вигляді матриці m×2 у лівій частині другої області введення. В кожному рядку спочатку записується номер першої вершини дуги (хвоста, джерела), а потім номер другої вершини (вістря, приймача). У цих стовпцях повинні бути натуральні числа від 1 до n включно. Числа розділяйте пробілами. У правій частині цієї області введення задаються ваги дуг − дійсні числа. Якщо цей стовпчик не заданий, то всі ваги вважаються одинаковими (одиничними). Загальна кількість чисел у кожному з цих стовпців визначає потужність орграфа m − кількість дуг.

І, нарешті, ще два поля введення − це номери стартової та кінцевої вершин для знаходження найкоротшого шляху. Якщо вони не задані, буде шукатися найкоротший шлях від першої вершини до останньої (з найбільшим номером).

Координати вершин
x   (пробіл)   y

Дуги та їхні ваги
v1  (пробіл)  v2 Вага

Початок та кінець шляху
Початок шляху s =     Кінець шляху t =