Как найти кратчайший путь в графе онлайн

Создание графа

С помощью данной программы можно онлайн нарисовать любой граф (ориентированный, неориентированный, с петлями), сетевой график, дерево, граф состояний или блок-схему. Во вкладке Примеры графов можно ознакомиться с возможностями онлайн сервиса.

Граф можно нарисовать или задать в виде матрицы или схемы (меню Действия).

Также доступно:

• Поиск кратчайшего пути с помощью алгоритма Дейкстры, задача о кратчайшем пути (см. вкладку Параметры графа).
• Построить дерево.
• Построить дерево по коду Прюфера (затем можно будет найти его инверсию).

• Редактор графа
• Параметры графа
• Решение
• Примеры реализаций
• Оформление Word

Инструкция к сервису по рисованию графа

Для добавления вершины на графическое полотно необходимо использовать соответствующую фигуре кнопку Добавить. Если название вершины не задано, будет показан ее номер. По умолчанию, нумерация начинается с номера 1. Чтобы нумерация начиналась с 0, необходимо снять отметку с пункта Нумерация вершин с №1. Название вершины может содержать символьную строку (перенос строк осуществляется через символ |).

Чтобы соединить вершины, их необходимо предварительно выбрать (один клик мыши по объекту), а затем нажать на кнопку Соединить. Если выбрана одна вершина, то будет создана петля. У выбранных элементов (вершин или дуг) можно изменить свойства или удалить их.

Построенный граф можно сохранить в формате docx или png.

Основные определения

В математической теории графов и информатике граф представляет собой совокупность объектов со связями между ними. Граф G задается множеством точек (вершин) X={x1,…,xn} и множеством линий (ребер) A={a1,…,am}, соединяющих между собой все или часть этих точек. На данный момент в сервисе для графического отображения вершин используются следующие фигуры: круг, квадрат и треугольник. Каждая вершина может иметь собственный вид: цвет и толщина линии, фон и размеры. Для изменения характеристик вершины необходимо выделить ее левой кнопки мыши и нажать на кнопку Свойства.

Ребра графа – линии, соединяющие вершины. Чтобы соединить вершины, необходимо выбрать одну или две из них. Каждое ребро графа имеет собственные свойства: цвет и толщина линии, значение (отображается поверх ребра).

Ребро графа называется неориентированным, если порядок расположения его концов (направление стрелок) в графе не принимается во внимание. Ребро графа называется ориентированным, если этот порядок существенен. Ориентированное ребро называют также дугой графа. Две вершины, соединённые дугой или ребром называются смежными. Для задания дуги необходимо при соединении вершин отметить пункт концевой маркер →. Для изменения типа дуги необходимо выделить ее левой кнопки мыши и нажать на кнопку Свойства.

С каждым ребром можно связать число или символ — вес ребра. Для задачи коммивояжера это может быть расстояние между городами, а для транспортной сети – стоимость проезда. Такой граф называется взвешенным.

Для каждого графа G(Х) существует обратный граф G^-1(Х), полученный изменением ориентации каждого из ребер графа G(Х) на противоположную.

Петлей называется ребро g(xi,xi), у которого начальная и конечная вершины совпадают. Петля обычно считается неориентированной. Для создания петли необходимо выделить только одну вершину и нажать на кнопку Соединить.

Область применения

Поскольку граф очень удобная математическая модель, с его помощью можно решать различные задачи из разных областей. С другой стороны, граф – это и информационная модель, с помощью его удобно представлять информацию графически. Посмотреть примеры графов можно в этом разделе.

Сеть это граф, в котором вершины связаны между собой по принципу «многие ко многим».

Примером ориентированного графа являются блок-схемы алгоритмов.

Задача о кратчайшем пути между парой вершин

Требуется найти кратчайший путь из заданной вершины s в заданную вершину d. Для этого необходимо будет выделить вершины s и d, а затем выполнить команду Разрез сети. Используется алгоритм Дейкстры (Dijkstra’s algorithm, 1959). Для более подробного решения по шагам, используйте вкладу Параметры графа.

Пример. Задан обыкновенный граф с 7 вершинами и рёбрами: (1,3), (1,4), (2,6), (3,6), (4,5), (5,6), (5,7), (6,7). Вычислить и записать кратчайший путь (через 1 пробел) от вершины 1 до вершины 2.

Построение дерева

Для преобразования созданного графа в дерево (организационная диаграмма), используйте команду Преобразовать в дерево. Также можно создать дерево заново, использую следующий сервис. Для этого в каждой строке укажите вершины в формате:v1-v2. Текст к вершине задается командой v1=name.

Отображать индексы вершин

1-2
1-3
2-4
1=Директор
2=Финансовый директор
3=Бухгалтер
4=Экономист

Для решения задач динамического программирования, условие может выглядеть так.

На данной сети дорог имеется несколько маршрутов, по которым можно доставлять груз из пункта 1 в пункт 10. Известны стоимости с_ij перевозки единицы груза между пунктами сети.

Требуется:

1. методом динамического программирования найти за сети наиболее экономный маршрут доставки груза из пункта 1 в пункт 10 и соответствующие ему затраты;
2. выписать оптимальные маршруты перевозки груза из всех остальных пунктов сети в пункт 10 и указать отвечающие им минимальные затраты на доставку.

12345678910
7 3 5 298 34 715 21 694 38

Для решения необходимо задать сеть (удобнее в виде схемы через меню Действия) и отметить пункт задача о кратчайшем пути из вершины 10.

Список литературы

1. Кориков А.М., Сафьянова Е.Н. Основы системного анализа и теории систем: Учебное пособие. – Томск: изд-во Том. ун-та, 1989. – 207 с.
2. Оре О. Теория графов. – М.: Наука, 1980. – 352 с.
3. Основы кибернетики. Математические основы кибернетики / Под. ред. К.А. Пупкова. – М.: Высш. школа, 1974. – 416 с.
4. Горбатов В.А. Основы дискретной математики. – М.: Высш. школа, 1986. – 312 с.
5. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.
6. Кузин Л.Т. Основы кибернетики.: В 2 т. Т.2. Основы кибернетических моделей. – М.: Энергия, 1979. – 584 с.
7. Шевелев Ю.П. Высшая математика 5. Дискретная математика. Ч.1: Теория множеств. Булева алгебра (для автоматизированной технологии обучения): Учебное пособие. – Томск: Том. гос. ун-т систем управления и радиоэлектроники, 1998. – 114 с.
8. Восстановление дерева по коду Прюфера