Алгоритмы на графах

остова графа: алгоритм Крускала.
Задача о лабиринте и поиск в

глубину на неориентированном графе.

августа 2002) — нидерландский учёный, идеи которого оказали влияние на развитие компьютерной индустрии.

расстояние от одной из вершин графа до всех остальных.
Алгоритм

работает только для графов без рёбер отрицательного веса.
Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

веса. Найти кратчайшие пути от некоторой вершины а до всех

остальных вершин этого графа

Граф называется взвешенным или нагруженным, если каждому ребру поставлено в соответствии некоторое число w (вес).

до  а. Алгоритм работает пошагово — на каждом шаге он «посещает»

одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Метка самой вершины  а  полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку.

Рассматриваем всевозможные маршруты из u. Вершины, в которые ведут рёбра из u, называются соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины.
Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

ко всем остальным вершинам и восстановить кратчайшие пути к ним.

ко всем остальным вершинам и восстановить кратчайшие пути к ним.

ко всем остальным вершинам и восстановить кратчайшие пути к ним.

ко всем остальным вершинам и восстановить кратчайшие пути к ним.

d(1,2)=7
d(1,3)=9
d(1,4)=20
d(1,5)=20
d(1,6)=11

> ', i,' = ', distance[i]) else writeln(m,' > ', i,' = ', 'маршрут недоступен'); end; {главное тело

программы} begin clrscr; write('Начальная вершина >> '); read(start); Dijkstra(GR, start); end.

Labs,  Lucent Technologies, Room 2C-281, Murray Hill, NJ 07974, USA
Алгоритм Крускала (или алгоритм

Краскала) — алгоритм построения минимального остовного дерева взвешенного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.

деревьев
Минимальным остовным деревом называется остовное дерево с минимальным общим весом

его ребер.

2

3

5

2

1

4

3

6

2

ребер c: E -> R.
Выход: минимальный остов S=(V,T).

Формулировка задачи

вершины ребра, номер конечной вершины ребра.
Данный список упорядочивается в порядке

возрастания длин ребер.
Просматривается список E и выбирается из него ребро с минимальной длиной, еще не включенное в результирующее дерево S и не образующее цикла с уже построенными ребрами.
Если все вершины графа включены в дерево S и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.

множество ребер Ti:


Положим T=Tm. Выдать в качестве результата граф S=(V,T).

Шаги алгоритма

(g,e), (g,c), (e,d), (a,b), (f,g)}

минимальный остов неориентированного взвешенного графа.

неориентированного взвешенного графа.

до остальных вершин

Вариант 1
Найти минимальное расстояние от вершины 6 до

остальных вершин
Найти минимальный остов взвешенного графа

Вариант 2