Знаходження найкоротшого шляху між двома вершинами в орієнтованому графі використовуючи алгоритм Дейкстри

Delphi-проект розроблено за проханням користувача на ім'я andrey_khorolskiy («...Бажано передбачити можливість пошуку найкоротшого маршруту не тільки між початковою та кінцевою вершинами, але і між початковою і проміжною без пошуку маршруту до кінцевої...») і реалізує процес знаходження найкоротшого шляху між двома вершинами в орієнтованому графі, використовуючи для цього алгоритм Дейкстри.

Виходячи з того, що інтерфейс головної форми розглядуваного delphi-проекту аналогічний проектам, які реалізують інші алгоритми на графах, лише з однією відмінністю (панель інструментів міститься додаткове поле типу TEdit, в яке, способом введення з клавіатури, необхідно вказати номер вершини, для якої будується маршрут), то основні її елементи та процес побудови орієнтованого графа розглядати не будемо. Це все детально можна почитати перейшовши, наприклад, за посиланням Знаходження найкоротшого шляху від однієї вершини графа до всіх інших вершин в середовищі програмування delphi. А перейдемо до практики, тобто провіримо його роботу на конкретному прикладі.

Для цього, розглянемо деякий орієнтований граф, і припустимо, що для нього необхідно знайти мінімальний маршрут від вершини номер один, до вершини номер три.

Читати повністю

Рівняння кривої другого порядку що описує коло

Кривою другого порядку називається лінія, що визначається рівнянням другої степені щодо поточних декартових координат. У загальному випадку це рівняння записується в наступному вигляді:

де коефіцієнти  — дійсні числа і, крім того, принаймі одне із чисел або відмінне від нуля. В залежності від того, які значення приймають дані коефіцієнти, рівняння (1) визначає на площині коло, еліпс, гіперболу або параболу. Сьогодні покажемо, якими вони повинні бути для кола. Для цього, запишемо рівняння, яке описує коло радіуса  з центром в точці :

Розкривши дужки в рівнянні такого виду та виконавши деякі тотожні перетворення, перепишемо його в наступному вигляді:

Порівнюючи далі рівняння (3) із загальним рівнянням кривої другого порядку бачимо, що для того, щоб  рівняння (1) описувало коло необхідно, щоб для нього виконувались наступні дві умови: коефіцієнти при  та  повинні бути рівні між собою і член що містить добуток координат  повинен бути відсутнім.

Читати повністю

Відстань від точки до прямої на площині

Нехай на площині міститься пряма задана своїм рівнянням у загальному вигляді і деяка точка , що не лежить на даній прямій. Через точку  проведемо перпендикуляр до заданої прямої і позначимо точку їх перетину через . Тоді відстань від точки  до прямої буде дорівнювати відстані між точками  та .

Відстань від точки до прямої

Графічне представлення алгоритму знаходження відстані від точки до прямої

Виведемо формулу для обчислення відстані від точки до прямої. Для цього приведемо рівняння заданої прямої до виду рівняння прямої з кутовим коефіцієнтом:

Читати повністю

Точка перетину двох прямих на площині

Нехай дано дві прямі, задані своїми рівняннями в загальному вигляді і . Знайдемо точку перетину цих прямих.

Графічне представлення алгоритму знаходження точки перетину двох прямих

Так як ця точка належить кожній з двох даних прямих, то її координати повинні задовольняти як рівняння першої, так і рівняння другої прямої. Таким чином, для того щоб знайти координати точки перетину двох прямих, слід розв'язати систему рівнянь виду:

Читати повністю

Рівняння прямої яка проходить через дві задані точки

Нехай задані дві точки та через які проходить пряма і для якої, використовуючи їх координати, необхідно знайти її рівняння. Для цього припустимо, що . Відмітимо, що в такому випадку пряма не паралельна осі ординат. А, як нам уже відомо, рівняння будь-якої прямої яка проходить через точку і не паралельна осі  є рівняння виду:

Так як пряма проходить також і через точку , то координати даної точки повинні задовільняти цьому рівнянню. Підставляючи в рівняння (1), замість поточних координат, координати і , отримаємо . Звідси знаходимо:

Тобто кутовий коефіцієнт прямої дорівнює різниці ординат будь-яких двох її точок, розділеної на різницю абсцис цих точок. Підставивши знайдене значення в рівняння (1), отримаємо рівняння прямої, яка проходить через дві задані точки і :

Читати повністю

Рівняння прямої яка походить через задану точку

Нехай задані точка  і кутовий коефіцієнт , який визначає напрямок прямої лінії, що проходить через цю точку. Поставимо перед собою задачу, використовуючи відомі параметри, знайти рівняння прямої. Для цього, запишемо рівняння прямої з кутовим коефіцієнтом:

Відмітимо, що в даному рівнянні невідомим являється вільний член . Але виходячи з того, що пряма (1) проходить через точку , то координати цієї точки задовільняють рівняння прямої . Звідси отримаємо:

Підставляючи знайдене значення  в рівняння (1), отримаємо , звідки:

Таким чином, ми отримали рівняння прямої, яка проходить через точку  в заданому напрямку . Якщо ж розглядається задача, в якій задана тільки точка , то коефіцієнт  в рівнянні (3) може приймати будь-які значення, тобто рівняння (3) буде рівнянням будь-якої прямої, що проходить через точку  (за винятком прямої , паралельної осі ). Тому рівняння (3) при будь-яких  називається рівнянням пучка прямих, що проходять через точку .

Читати повністю

Умова паралельності та перпендикулярності двох прямих

Дві прямі і паралельні в тому і тільки тому випадку, коли утворюють рівні кути і з віссю . Тоді, або .

Дві прямі перпендикулярні в тому і тільки тому випадку, коли кут між ними дорівнює . Тоді, скориставшись формулою будемо мати:

Тобто зі сказаного вище випливає, що для того щоб дві прямі були паралельні, необхідно і достатньо, щоб їх кутові коефіцієнти були рівні. А для того щоб дві прямі були перпендикулярні, необхідно і достатньо, щоб їх кутові коефіцієнти були оберненими числами, з протилежними знаками.

Читати повністю

Наступна сторінка »