ТГиК-2019-Лекция-02.12.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

В данной лекции рассматриваются взвешенные ориентированные графы.

Введение

Что означает понятие "взвешенный граф" на практике? Вводится некая функция (весовая функция), которая каждому ребру графа ставит в соответствие некоторое вещественное число\[ \exists w: E \longrightarrow \mathbb{R} \]

Введём обозначение пути из вершины \(v_0\) в вершину \(v_k\)\[ p = <v_0, v_1, ..., v_k> \]

Тогда вес пути равен суммарному весу входящих в него ребер\[ w(p) = \sum^{k}_{i=0} {w(v_{i-1}, v_i)} \]

Введём понятие веса кратчайшего пути \(\delta(u,v)\)

\(\delta (u,v)= \begin{cases} min \mbox{ } {w(p): u \xrightarrow{p} v } \mbox{, если путь есть }\\ \infty \mbox{, если пути нет } \end{cases} \)

Тогда кратчайший путь - это путь, у которого \(w(p)= \delta (u,v)\), где \(p = <u, ..., v> \)

Какие есть вообще задачи на кратчайшие пути?

  • Задачи о кратчайших путях в одну вершину

Требуется найти кратчайшие пути в заданную целевую вершину \(t\), которые начинаются в каждой из вершин \(v\). Если поменять направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине.

  • Кратчайший путь между заданной парой вершин

Требуется найти кратчайший путь из заданной вершины \(u\) в заданную вершину \(v\). Если решена задача поиска кратчайших путей из заданной исходной вершины \(u\), то эта задача также решается. Более того, все известные для решения данной задачи алгоритмы имеют то же время работы в худшем случае, что и лучшие алгоритмы поиска кратчайших путей из одной вершины.

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

Требуется найти кратчайший путь из каждой вершины \(u\) в каждую вершину \(v\). Эту задачу также можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее. Кроме того, структура этой задачи представляет интерес сама по себе.

Ослабление (релаксация)

Процесс ослабления (relaxation) ребра \((u,v)\) заключается в следующей проверке: нельзя ли улучшить найденный к этому моменту кратчайший путь к вершине \(v\), проведя его через вершину \(u\), а также в обновлении \(d[v]\) и \(p[v]\) при наличии такой возможности. Ослабление может уменьшить оценку кратчайшего пути \(d[v]\) и обновить \(p[v]\) вершины \(v\). Приведенный ниже код выполняет ослабление ребра \((u,v)\) за время \(O(1)\).

Пусть у нас есть значение \( d[u], d[v] \mbox { и } \exists (u,v) \)

//если путь до вершины v больше, чем путь до вершины u и ребро (u,v), то присваиваем кратчайшему пути до v новое значение и устанавливаем для v нового предка
if d[v] > d[u] + w[u][v]: 
 d[v]=d[u]+w[u][v];
 p[v]=u;

Свойства кратчайших путей

Лемма 1

Все подпути кратчайшего пути являются кратчайшими путями.

Пусть \(p= <v_0, v_1, ..., v_k> \) - кратчайший путь \(v_0 \) в \(v_k \). Тогда \( \forall i, j : 0<i<j<k \mbox{: } p_{ij} = <v_i, v_{i+1}, ..., v_j> - \mbox { кратчайший путь из } v_i \mbox { в } v_j \)

Доказательство

1) \(v_0 \xrightarrow{p_{0i}} v_i \xrightarrow{p_{ij}} v_j \xrightarrow{p_{jk}} v_k\)

2) \(w(p) = w(p_{0i}) + w(p_{ij}) + w(p_{jk}) \)

3) Пусть есть путь \(p'_{ij} \mbox {: } w(p'_{ij}) < w(p_{ij}) \)

Следовательно, исходный путь - не кратчайший. Получим противоречие с условием

Лемма 2. Неравенство треугольника

\( \forall (u,v) \in E \mbox{ } \delta (s,v) \le \delta (s,u) + w(u,v) \)

Лемма 3. Свойство верхней границы

\( \forall v \in V \mbox{ } d[v] \ge \delta (s,v), \mbox{ при этом если } d[v] = \delta (s,v)\mbox{, } d[v] \mbox{ больше не меняется} \)

Лемма 4. Свойство отсутствия границы

Если из вершины \(s\) в вершину \(v\) нет пути, то всегда выполняется соотношение \(d[v]=\delta(s,v)=\infty \)

Лемма 5. Свойство сходимости

Если \( s \rightsquigarrow u \longrightarrow v\) - кратчайший путь, то для некоторых \( u,v \in V \mbox{ } d[u] = \delta (s,u) \mbox{ до ослабления } (u,v) \mbox{ и } d[v] = \delta (s,v) \mbox{ после ослабления} \)

Лемма 6. Свойство ослабления пути

Если \( \forall v \in V : d[v] = \delta (s,v) \), то подграф \(G_p\) - дерево кратчайших путей из \(S\)

Алгоритм Дейкстры

Алгоритм Дейкстры позволяет найти кратчайшие пути и построить дерево кратчайших путей во взвешенном ориентированном графе \(G=(V,E)\)

import math

d = [math.inf] * 5
p = [-1] * 5
queue = [0, 1, 2, 3, 4]

d[0] = 0

while queue:
    key_min = queue[0]
    min_val = d[key_min]
    for n in range(1, len(queue)):
        if d[queue[n]] < min_val:
            key_min = queue[n]  
            min_val = d[key_min]
    cur = key_min
    queue.remove(cur)
    print(cur)
    
    for i in G[cur].keys():
        alternate = G[cur][i] + d[cur]
        if d[i] > alternate:
            d[i] = alternate
            p[i] = cur

Сложность алгоритма

Если вершины хранятся в простом массиве и для поиска минимума используется алгоритм линейного поиска, временная сложность алгоритма Дейкстры составляет \( O ( |V|^2) \)

Если же используется очередь с приоритетами, реализованная на основе двоичной кучи (или на основе set), то мы получаем \(O( |Е|*log(|V|)) \)

Если же очередь с приоритетами была реализована на основе кучи Фибоначчи, получается наилучшая оценка сложности \(O( |V|*log(|V|)+|E|) \)

Корректность алгоритма Дейкстры

Предположим, алгоритм был запущен на некотором графе из вершины \(u\) и выдал неверное значение расстояния для некоторых вершин, причем \(v\) — первая из таких вершин (первая в смысле порядка, в котором алгоритм выплевывал вершины). Пусть \(k\) — ее предок в кратчайшем пути из \(u\) в \(v\). Расстояние до \(k\)подсчитано верно по предположению.

1. Пусть \(d'[k]<d[v]\)

Тогда рассмотрим последнюю релаксацию ребра, ведущего в \(v \mbox{: } (s,v)\). Расстояние до \(s\) было подсчитано верно, значит, существует путь из \(u\) в \(v\) веса \(d[s] + w(s,v) = d'[v]<d[v] \). Получим противоречие по лемме 2.

2. Пусть \(d'[k]>d[v]\)

Тогда рассмотрим момент обработки вершины \(k\). В этот момент было релаксировано ребро \((k,v)\) и, соответственно, текущая оценка расстояния до вершины \(v\) стала равной \(d[v]\), а в ходе следующих релаксаций она не могла уменьшиться. Противоречие по лемме 3.

Алгоритм Флойда-Уоршелла

рис.1

Динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.

\(D\) - это матрица, в которой элемент \([i,j]\) содержит в себе вес пути от вершины с номером \(i+1\) до вершины с номером \(j+1\).

\(P\) - это матрица, в которой если \([i,j]=i+1\), то существует путь от вершины с номером \(i+1\) до вершины с номером \(j+1\), а если \([i,j]=-1\), то путь не существует.

D = [[0, 3, 8, inf, -4],
     [inf, 0, inf, 1, 7],
     [inf, 4, 0, inf, inf],
     [2, inf, -5, 0, inf],
     [inf, inf, inf, 6, 0]]

P = [[-1, 1, 1, -1, 1],
     [-1, -1, -1, 2, 2],
     [-1, 3, -1, -1, -1],
     [4, -1, 4, -1, -1],
     [-1, -1, -1, 5, -1]]
n = 5
for k in range(5): 
    for i in range(5): 
        for j in range(5): 
            if D[i][j] >  D[i][k]+ D[k][j]:
                D[i][j] = D[i][k]+ D[k][j]
                P[i][j] = P[k][j]