Граф с весами рёбер

Граф с весами рёбер

Граф — это схема из точек (вершин) и соединяющих их линий (рёбер). В обычном графе ребро лишь показывает, что две вершины связаны между собой. Но связь бывает «дороже» или «дешевле»: путь между городами может быть длиннее или короче, билет — дороже или дешевле. Чтобы это учесть, рёбрам приписывают числа — веса.

Что такое вес ребра

Вес ребра — это число, которое выражает «стоимость» связи: длину дороги в километрах, время в пути в минутах, цену билета в рублях. Граф, у которого все рёбра имеют веса, называют взвешенным. Вес целого пути по нескольким рёбрам равен сумме весов этих рёбер. Поэтому, чтобы сравнить два пути, складывают веса вдоль каждого из них и смотрят, где сумма меньше.

Поиск самого короткого пути

Часто нужно найти путь с наименьшим суммарным весом. Рассмотрим, как добраться из вершины А в вершину Б. Прямое ребро А — Б весит 5. Но можно пойти в обход через вершину В:

Второй путь длиннее по числу рёбер — он проходит через две связи вместо одной, — но его суммарный вес меньше, всего 3. Значит, по расстоянию он выгоднее. Чтобы продолжить дорогу до вершины Г, к выбранному пути добавится ребро Б — Г: А -> В -> Б -> Г = 2 + 1 + 4 = 7. Так шаг за шагом и набирается общий вес маршрута.

Где это пригождается

Взвешенные графы описывают карты дорог, схемы метро, сети передачи данных. Программы-навигаторы как раз ищут в таких графах путь наименьшего веса — самый быстрый или самый короткий маршрут. Поэтому умение складывать веса вдоль пути и сравнивать суммы — основа таких расчётов.

Как перебирать пути

Чтобы вручную найти кратчайший путь в небольшом графе, выписывают все возможные маршруты из начальной вершины в конечную, считают вес каждого и выбирают наименьший. В нашем примере из А в Б было всего два пути, и сравнить их оказалось просто. В больших графах путей становится очень много, и перебирать их вручную долго — тогда на помощь приходят специальные алгоритмы, которые делают это быстро и не пропускают ни одного варианта. Но идея у них та же самая: найти маршрут с наименьшей суммой весов рёбер.

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

Кратко о главном

• Вес ребра — число, выражающее «стоимость» связи (длину, время, цену).
• Граф со всеми весами рёбер называют взвешенным.
• Вес пути равен сумме весов рёбер, по которым он проходит.
• Кратчайший путь определяют по наименьшей сумме весов, а не по числу рёбер.