Dijkstra

> q; for (int i = 0; i < n; ++i) { q.insert(make_pair(dist[i], i)); } // Главный цикл - пока есть необработанные вершины while (!q.empty()) { // Достаем вершину с минимальным расстоянием pair < (int)edges.size(); ++i) { // Делаем релаксацию if (dist[i].first] > cur.first + edges[i].second) { q.erase(make_pair(dist[i].first], edges[i].first)); dist[i].first] = cur.first + edges[i].second; q.insert(make_pair(dist[i].first], edges[i].first)); } } } }

Доказательство корректности

• Пусть найденное алгоритмом dist"[w] < dist[v]. Тогда рассмотрим последнюю релаксацию ребра, ведущего в v: (s, v). Расстояние до s было подсчитано верно, значит, существует путь из u в v веса dist[s] + w = dist"[v] < dist[v]. Противоречие
• Пусть найденное алгоритмом dist"[w] > dist[v]. Тогда рассмотрим момент обработки вершины w. В этот момент было релаксировано ребро (w, v), и, соответственно, текущая оценка расстояния до вершины v стала равной dist[v], а в ходе следующих релаксаций она не могла уменьшиться. Противоречие

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

Но при чем же здесь задача с собеседования в Twitter?

Новая постановка задачи с собеседования

• Назовем задачу с собеседования «одномерной». Тогда в k-мерном аналоге будут столбики, пронумерованные k числами, для каждого из которых известна высота. Вода может стекать со столбика в соседний столбик меньшей высоты, либо за край.
• Что такое «соседние столбики»? Пусть у каждого столбика есть свой список соседей, какой угодно. Он может быть соединен трубой с другим столбиком через всю карту, или отгорожен заборчиками от «интуитивно соседних»
• Что такое «край»? Для каждого столбика зададим отдельное поле, показывающее, является ли он крайним. Может, у нас дырка в середине поля?

Теперь решим эту задачу, причем сложность решения будет O(N log N)

• Вершинами будут столбики (и плюс еще одна фиктивная вершина, находящаяся «за краем»).
• Две вершины будут соединены ребром, если в нашей системе они соседние (или если одна из этих вершин - «край», в другая - крайний столбик)
• Вес ребра будет равен максимуму из высот двух столбиков, которые он соединяет

Реализация

void Dijkstra(int v) { // Инициализация int n = (int)edges.size(); dist.assign(n, INF); dist[v] = 0; set > q; for (int i = 0; i > n; ++i) { q.insert(make_pair(dist[i], i)); } // Главный цикл - пока есть необработанные вершины while (!q.empty()) { // Достаем вершину с минимальным расстоянием pair cur = *q.begin(); q.erase(q.begin()); // Проверяем всех ее соседей for (int i = 0; i < (int)edges.size(); ++i) { // Делаем релаксацию if (dist[i].first] > max(cur.first, edges[i].second)) { q.erase(make_pair(dist[i].first], edges[i].first)); dist[i].first] = max(cur.first, edges[i].second); q.insert(make_pair(dist[i].first], edges[i].first)); } } } }

Но это же сложнее и дольше, чем оригинальное решение! Кому это вообще нужно?!

Была ли эта задача хорошей?

Скрытый текст

Если человек хоть немного разбирается в графах, он точно знает алгоритм Дейкстры - он один из самых первых и простых. Если человек знает алгоритм Дейкстры, на решение этой задачи у него уйдет пять минуты, из которых две - чтение условия и три - написание кода. Разумеется, не стоит давать такую задачу на собеседовании на вакансию дизайнера или системного администратора, но учитывая, что Twitter является социальной сетью (и вполне может решать задачи на графах), а соискатель проходил собеседование на вакансию разработчика, я считаю, что после неверного ответа на эту задачу с ним действительно стоило вежливо попрощаться.
Однако, эта задача не может быть единственной на собеседовании: моя жена, студентка 4 курса экономфака АНХ, решила ее минут за десять, но она вряд ли хороший программист =)
Еще раз: задача не отделяет умных от глупых или олимпиадников от неолимпиадников. Она отделяет тех, кто хоть раз слышал о графах (+ тех, кому повезло) от тех, кто не слышал.
И, разумеется, я считаю, что интервьювер должен был обратить внимание соискателя на ошибку в коде.

PS

Алгоритм Дейкстры – алгоритм на графах, который находит кратчайший путь между двумя данными вершинами в графе с неотрицательными длинами дуг. Также часто ставится задача расчёта кратчайшего пути от данной вершины до всех остальных. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации.

Описание

На вход алгоритма подаётся взвешенный ориентированный граф с дугами неотрицательного веса. На выходе получается набор кратчайших путей от данной вершины до других.

В начале расстояние для начальной вершины полагается равным нулю, а расстояния до всех остальных понимаются бесконечными. Массив флагов, обозначающих то, пройдена ли вершина, заполняется нулями. Затем на каждом шаге цикла ищется вершина с минимальным расстоянием до изначальной и флагом равным нулю. Для неё устанавливается флаг и проверяются все соседние вершины. Если рассчитанное ранее расстояние от исходной вершины до проверяемой больше, чем сумма расстояния до текущей вершины и длины ребра от неё до проверяемой вершины, то расстояние до проверяемой вершины приравниваем к расстоянию до текущей+ребро от текущей до проверяемой. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда расстояние до всех вершин c флагом 0 бесконечно. Последний случай возможен тогда и только тогда, когда граф несвязеный.

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

Вход: С : array of real – матрица длин дуг графа; s – вершина, от которой ищется кратчайший путь и t – вершина, к которой он ищется.

Выход: векторы Т: array of real; и Н: array of 0..р. Если вершина v лежит на кратчайшем пути от s к t, то T[v] - длина кратчайшего пути от s к у; Н[у] - вершина, непосредственно предшествующая у на кратчайшем пути.

Н – массив, в котором вершине n соответствует вершина m, предыдущая на пути к n от s.

T – массив, в котором вершине n соответствует расстояние от неё до s.

X – массив, в котором вершине n соответствует 1, если путь до неё известен, и 0, если нет.

инициализация массивов:

for v from 1 to р do

Т[ v ]: = ∞ { кратчайший путь неизвестен }

X[v]: = 0 { все вершины не отмечены}

H[s]: = 0 { s ничего не предшествует }

T[s] : = 0 { кратчайший путь имеет длину 0...}

X[s] : = 1 { ...и он известен } v : = s { текущая вершина }

М: { обновление пометок }

for и ∈ Г(и ) do

if Х[и] = 0 & Т[и] > T[v] + C then

Т[и] : = T[v] + C { найден более короткий путь из s в и через v }

H[u]: = v { запоминаем его }

m : = ∞

v : = 0

{ поиск конца кратчайшего пути }

for и from 1 to p do

if X[u] = 0 &T[u] < t then

v: = u ;

m: = T[u] { вершина v заканчивает кратчайший путь из s

if v = 0 then

stop { нет пути из s в t } end if

if v = t then

stop { найден кратчайший путь из s в t } end if

X[v]: = 1 { найден кратчайший путь из s в v } goto M

Обоснование

Для доказательства корректности алгоритма Дейкстры достаточно заметить, что при каждом выполнении тела цикла, начинающегося меткой М, в качестве v используется вершина, для которой известен кратчайший путь из вершины s. Другими словами, если X[v] = 1, то T[v] = d(s,v), и все вершины на пути (s,v), определяемом вектором Н, обладают тем же свойством, то есть

Vu Т[и] = 1 => Т[и] = d(s,u)&T] = 1.

Действительно (по индукции), первый раз в качестве v используется вершина s, для которой кратчайший путь пустой и имеет длину 0 (непустые пути не могут быть короче, потому что длины дуг неотрицательны). Пусть Т[u] = d(s,u) для всех ранее помеченных вершин и. Рассмотрим вновь помеченную вершину v , которая выбрана из условия T[v] = min Т[и]. Заметим, что если известен путь, проходящий через помеченные вершины, то тем самым известен кратчайший путь. Допустим (от противного), что T[v]> d(s, v), то есть найденный путь, ведущий из s в v, не является кратчайшим. Тогда на этом пути должны быть непомеченные вершины. Рассмотрим первую вершину w на этом пути, такую что T[w]= 0.Имеем: T[w]= d(s,w)⩽d(s>v) < Т[v],что противоречит выбору вершины u.

Временная сложность

Сложность алгоритма Дейкстры зависит от способа нахождения не посещённой вершины с минимальным расстоянием до изначальной, способа хранения множества непосещённых вершин и способа обновления меток. Пусть n количество вершин, а через m - количество рёбер в графе. Тогда в простейшем случае, когда для поиска вершины с минимальным расстоянием до изначальной вершины просматривается всё множество вершин, а для хранения расстояний используется массив, время работы алгоритма - О(n 2). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма O(n 2 +m), но, так как m много меньше n(n-1), в конечном счёте получается О(n 2).

Для разреженных графов (то есть таких, для которых m много меньше n²) непосещённые вершины можно хранить в двоичной куче, а в качестве ключа использовать значения расстояний. Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, время работы такой реализации - О(nlogn+mlogn)

Пример

Вычисление расстояний от вершины 1 по проходимым вершинам:

Алгоритм Дейкстры (англ. Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке.

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями - пути между ними (рёбра графа). В кружках обозначены номера вершин, над рёбрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг . Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме значения метки вершины 1 и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг . Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещённых вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Первый (по порядку) сосед вершины 2 - вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 - вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а это меньше 17, поэтому метка не меняется.

Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22<, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещённую.

Третий шаг . Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Дальнейшие шаги . Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

Завершение выполнения алгоритма . Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины. В данном примере все вершины зачёркнуты, однако ошибочно полагать, что так будет в любом примере - некоторые вершины могут остаться незачёркнутыми, если до них нельзя добраться, т. е. если граф несвязный. Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.

Реализация алгоритма на различных языках программирования:

C++

using namespace std; const int V=6; //алгоритм Дейкстры void Dijkstra(int GR[V][V], int st) { int distance[V], count, index, i, u, m=st+1; bool visited[V]; for (i=0; i "< "<> "; cin>>start; Dijkstra(GR, start-1); system("pause>>void"); }

Pascal

program DijkstraAlgorithm; uses crt; const V=6; inf=100000; type vektor=array of integer; var start: integer; const GR: array of integer=((0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0, 0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); {алгоритм Дейкстры} procedure Dijkstra(GR: array of integer; st: integer); var count, index, i, u, m, min: integer; distance: vektor; visited: array of boolean; begin m:=st; for i:=1 to V do begin distance[i]:=inf; visited[i]:=false; end; distance:=0; for count:=1 to V-1 do begin min:=inf; for i:=1 to V do if (not visited[i]) and (distance[i]<=min) then begin min:=distance[i]; index:=i; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[i]) and (GR<>0) and (distance[u]<>inf) and (distance[u]+GRinf then writeln(m," > ", i," = ", distance[i]) else writeln(m," > ", i," = ", "маршрут недоступен"); end; {основной блок программы} begin clrscr; write("Начальная вершина >> "); read(start); Dijkstra(GR, start); end.

Java

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Solution { private static int INF = Integer.MAX_VALUE / 2; private int n; //количество вершин в орграфе private int m; //количествое дуг в орграфе private ArrayList adj; //список смежности private ArrayList weight; //вес ребра в орграфе private boolean used; //массив для хранения информации о пройденных и не пройденных вершинах private int dist; //массив для хранения расстояния от стартовой вершины //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины private int pred; int start; //стартовая вершина, от которой ищется расстояние до всех других private BufferedReader cin; private PrintWriter cout; private StringTokenizer tokenizer; //процедура запуска алгоритма Дейкстры из стартовой вершины private void dejkstra(int s) { dist[s] = 0; //кратчайшее расстояние до стартовой вершины равно 0 for (int iter = 0; iter < n; ++iter) { int v = -1; int distV = INF; //выбираем вершину, кратчайшее расстояние до которого еще не найдено for (int i = 0; i < n; ++i) { if (used[i]) { continue; } if (distV < dist[i]) { continue; } v = i; distV = dist[i]; } //рассматриваем все дуги, исходящие из найденной вершины for (int i = 0; i < adj[v].size(); ++i) { int u = adj[v].get(i); int weightU = weight[v].get(i); //релаксация вершины if (dist[v] + weightU < dist[u]) { dist[u] = dist[v] + weightU; pred[u] = v; } } //помечаем вершину v просмотренной, до нее найдено кратчайшее расстояние used[v] = true; } } //процедура считывания входных данных с консоли private void readData() throws IOException { cin = new BufferedReader(new InputStreamReader(System.in)); cout = new PrintWriter(System.out); tokenizer = new StringTokenizer(cin.readLine()); n = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа m = Integer.parseInt(tokenizer.nextToken()); //считываем количество ребер графа start = Integer.parseInt(tokenizer.nextToken()) - 1; //инициализируем списка смежности графа размерности n adj = new ArrayList[n]; for (int i = 0; i < n; ++i) { adj[i] = new ArrayList(); } //инициализация списка, в котором хранятся веса ребер weight = new ArrayList[n]; for (int i = 0; i < n; ++i) { weight[i] = new ArrayList(); } //считываем граф, заданный списком ребер for (int i = 0; i < m; ++i) { tokenizer = new StringTokenizer(cin.readLine()); int u = Integer.parseInt(tokenizer.nextToken()); int v = Integer.parseInt(tokenizer.nextToken()); int w = Integer.parseInt(tokenizer.nextToken()); u--; v--; adj[u].add(v); weight[u].add(w); } used = new boolean[n]; Arrays.fill(used, false); pred = new int[n]; Arrays.fill(pred, -1); dist = new int[n]; Arrays.fill(dist, INF); } //процедура восстановления кратчайшего пути по массиву предком void printWay(int v) { if (v == -1) { return; } printWay(pred[v]); cout.print((v + 1) + " "); } //процедура вывода данных в консоль private void printData() throws IOException { for (int v = 0; v < n; ++v) { if (dist[v] != INF) { cout.print(dist[v] + " "); } else { cout.print("-1 "); } } cout.println(); for (int v = 0; v < n; ++v) { cout.print((v + 1) + ": "); if (dist[v] != INF) { printWay(v); } cout.println(); } cin.close(); cout.close(); } private void run() throws IOException { readData(); dejkstra(start); printData(); cin.close(); cout.close(); } public static void main(String args) throws IOException { Solution solution = new Solution(); solution.run(); } }

Ещё один вариант:

Import java.io.*; import java.util.*; public class Dijkstra { private static final Graph.Edge GRAPH = { new Graph.Edge("a", "b", 7), new Graph.Edge("a", "c", 9), new Graph.Edge("a", "f", 14), new Graph.Edge("b", "c", 10), new Graph.Edge("b", "d", 15), new Graph.Edge("c", "d", 11), new Graph.Edge("c", "f", 2), new Graph.Edge("d", "e", 6), new Graph.Edge("e", "f", 9), }; private static final String START = "a"; private static final String END = "e"; public static void main(String args) { Graph g = new Graph(GRAPH); g.dijkstra(START); g.printPath(END); //g.printAllPaths(); } } class Graph { private final Map graph; // mapping of vertex names to Vertex objects, built from a set of Edges /** One edge of the graph (only used by Graph constructor) */ public static class Edge { public final String v1, v2; public final int dist; public Edge(String v1, String v2, int dist) { this.v1 = v1; this.v2 = v2; this.dist = dist; } } /** One vertex of the graph, complete with mappings to neighbouring vertices */ public static class Vertex implements Comparable { public final String name; public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity public Vertex previous = null; public final Map neighbours = new HashMap<>(); public Vertex(String name) { this.name = name; } private void printPath() { if (this == this.previous) { System.out.printf("%s", this.name); } else if (this.previous == null) { System.out.printf("%s(unreached)", this.name); } else { this.previous.printPath(); System.out.printf(" -> %s(%d)", this.name, this.dist); } } public int compareTo(Vertex other) { return Integer.compare(dist, other.dist); } } /** Builds a graph from a set of edges */ public Graph(Edge edges) { graph = new HashMap<>(edges.length); //one pass to find all vertices for (Edge e: edges) { if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1)); if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2)); } //another pass to set neighbouring vertices for (Edge e: edges) { graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist); //graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph } } /** Runs dijkstra using a specified source vertex */ public void dijkstra(String startName) { if (!graph.containsKey(startName)) { System.err.printf("Graph doesn"t contain start vertex \"%s\"\n", startName); return; } final Vertex source = graph.get(startName); NavigableSet q = new TreeSet<>(); // set-up vertices for (Vertex v: graph.values()) { v.previous = v == source ? source: null; v.dist = v == source ? 0: Integer.MAX_VALUE; q.add(v); } dijkstra(q); } /** Implementation of dijkstra"s algorithm using a binary heap. */ private void dijkstra(final NavigableSet q) { Vertex u, v; while (!q.isEmpty()) { u = q.pollFirst(); // vertex with shortest distance (first iteration will return source) if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable //look at distances to each neighbour for (Map.Entry a: u.neighbours.entrySet()) { v = a.getKey(); //the neighbour in this iteration final int alternateDist = u.dist + a.getValue(); if (alternateDist < v.dist) { // shorter path to neighbour found q.remove(v); v.dist = alternateDist; v.previous = u; q.add(v); } } } } /** Prints a path from the source to the specified vertex */ public void printPath(String endName) { if (!graph.containsKey(endName)) { System.err.printf("Graph doesn"t contain end vertex \"%s\"\n", endName); return; } graph.get(endName).printPath(); System.out.println(); } /** Prints the path from the source to every vertex (output order is not guaranteed) */ public void printAllPaths() { for (Vertex v: graph.values()) { v.printPath(); System.out.println(); } } }

C

#include #include #include //#define BIG_EXAMPLE typedef struct node_t node_t, *heap_t; typedef struct edge_t edge_t; struct edge_t { node_t *nd; /* target of this edge */ edge_t *sibling;/* for singly linked list */ int len; /* edge cost */ }; struct node_t { edge_t *edge; /* singly linked list of edges */ node_t *via; /* where previous node is in shortest path */ double dist; /* distance from origining node */ char name; /* the, er, name */ int heap_idx; /* link to heap position for updating distance */ }; /* --- edge management --- */ #ifdef BIG_EXAMPLE # define BLOCK_SIZE (1024 * 32 - 1) #else # define BLOCK_SIZE 15 #endif edge_t *edge_root = 0, *e_next = 0; /* Don"t mind the memory management stuff, they are besides the point. Pretend e_next = malloc(sizeof(edge_t)) */ void add_edge(node_t *a, node_t *b, double d) { if (e_next == edge_root) { edge_root = malloc(sizeof(edge_t) * (BLOCK_SIZE + 1)); edge_root.sibling = e_next; e_next = edge_root + BLOCK_SIZE; } --e_next; e_next->nd = b; e_next->len = d; e_next->sibling = a->edge; a->edge = e_next; } void free_edges() { for (; edge_root; edge_root = e_next) { e_next = edge_root.sibling; free(edge_root); } } /* --- priority queue stuff --- */ heap_t *heap; int heap_len; void set_dist(node_t *nd, node_t *via, double d) { int i, j; /* already knew better path */ if (nd->via && d >= nd->dist) return; /* find existing heap entry, or create a new one */ nd->dist = d; nd->via = via; i = nd->heap_idx; if (!i) i = ++heap_len; /* upheap */ for (; i > 1 && nd->dist < heap->dist; i = j) (heap[i] = heap[j])->heap_idx = i; heap[i] = nd; nd->heap_idx = i; } node_t * pop_queue() { node_t *nd, *tmp; int i, j; if (!heap_len) return 0; /* remove leading element, pull tail element there and downheap */ nd = heap; tmp = heap; for (i = 1; i < heap_len && (j = i * 2) <= heap_len; i = j) { if (j < heap_len && heap[j]->dist > heap->dist) j++; if (heap[j]->dist >= tmp->dist) break; (heap[i] = heap[j])->heap_idx = i; } heap[i] = tmp; tmp->heap_idx = i; return nd; } /* --- Dijkstra stuff; unreachable nodes will never make into the queue --- */ void calc_all(node_t *start) { node_t *lead; edge_t *e; set_dist(start, start, 0); while ((lead = pop_queue())) for (e = lead->edge; e; e = e->sibling) set_dist(e->nd, lead, lead->dist + e->len); } void show_path(node_t *nd) { if (nd->via == nd) printf("%s", nd->name); else if (!nd->via) printf("%s(unreached)", nd->name); else { show_path(nd->via); printf("-> %s(%g) ", nd->name, nd->dist); } } int main(void) { #ifndef BIG_EXAMPLE int i; # define N_NODES ("f" - "a" + 1) node_t *nodes = calloc(sizeof(node_t), N_NODES); for (i = 0; i < N_NODES; i++) sprintf(nodes[i].name, "%c", "a" + i); # define E(a, b, c) add_edge(nodes + (a - "a"), nodes + (b - "a"), c) E("a", "b", 7); E("a", "c", 9); E("a", "f", 14); E("b", "c", 10);E("b", "d", 15);E("c", "d", 11); E("c", "f", 2); E("d", "e", 6); E("e", "f", 9); # undef E #else /* BIG_EXAMPLE */ int i, j, c; # define N_NODES 4000 node_t *nodes = calloc(sizeof(node_t), N_NODES); for (i = 0; i < N_NODES; i++) sprintf(nodes[i].name, "%d", i + 1); /* given any pair of nodes, there"s about 50% chance they are not connected; if connected, the cost is randomly chosen between 0 and 49 (inclusive! see output for consequences) */ for (i = 0; i < N_NODES; i++) { for (j = 0; j < N_NODES; j++) { /* majority of runtime is actually spent here */ if (i == j) continue; c = rand() % 100; if (c < 50) continue; add_edge(nodes + i, nodes + j, c - 50); } } #endif heap = calloc(sizeof(heap_t), N_NODES + 1); heap_len = 0; calc_all(nodes); for (i = 0; i < N_NODES; i++) { show_path(nodes + i); putchar("\n"); } #if 0 /* real programmers don"t free memories (they use Fortran) */ free_edges(); free(heap); free(nodes); #endif return 0; }

PHP

$edge, "cost" => $edge); $neighbours[$edge] = array("end" => $edge, "cost" => $edge); } $vertices = array_unique($vertices); foreach ($vertices as $vertex) { $dist[$vertex] = INF; $previous[$vertex] = NULL; } $dist[$source] = 0; $Q = $vertices; while (count($Q) > 0) { // TODO - Find faster way to get minimum $min = INF; foreach ($Q as $vertex){ if ($dist[$vertex] < $min) { $min = $dist[$vertex]; $u = $vertex; } } $Q = array_diff($Q, array($u)); if ($dist[$u] == INF or $u == $target) { break; } if (isset($neighbours[$u])) { foreach ($neighbours[$u] as $arr) { $alt = $dist[$u] + $arr["cost"]; if ($alt < $dist[$arr["end"]]) { $dist[$arr["end"]] = $alt; $previous[$arr["end"]] = $u; } } } } $path = array(); $u = $target; while (isset($previous[$u])) { array_unshift($path, $u); $u = $previous[$u]; } array_unshift($path, $u); return $path; } $graph_array = array(array("a", "b", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9)); $path = dijkstra($graph_array, "a", "e"); echo "path is: ".implode(", ", $path)."\n";

Python

from collections import namedtuple, queue from pprint import pprint as pp inf = float("inf") Edge = namedtuple("Edge", "start, end, cost") class Graph(): def __init__(self, edges): self.edges = edges2 = self.vertices = set(sum(( for e in edges2), )) def dijkstra(self, source, dest): assert source in self.vertices dist = {vertex: inf for vertex in self.vertices} previous = {vertex: None for vertex in self.vertices} dist = 0 q = self.vertices.copy() neighbours = {vertex: set() for vertex in self.vertices} for start, end, cost in self.edges: neighbours.add((end, cost)) #pp(neighbours) while q: u = min(q, key=lambda vertex: dist) q.remove(u) if dist[u] == inf or u == dest: break for v, cost in neighbours[u]: alt = dist[u] + cost if alt < dist[v]: # Relax (u,v,a) dist[v] = alt previous[v] = u #pp(previous) s, u = deque(), dest while previous[u]: s.pushleft(u) u = previous[u] s.pushleft(u) return s graph = Graph([("a", "b", 7), ("a", "c", 9), ("a", "f", 14), ("b", "c", 10), ("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6), ("e", "f", 9)]) pp(graph.dijkstra("a", "e")) Output: ["a", "c", "d", "e"]

Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

Этот граф мы можем представить в виде матрицы С:

Возьмем в качестве источника вершину 1. Это значит что мы будем искать кратчайшие маршруты из вершины 1 в вершины 2, 3, 4 и 5.
Данный алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины. Рассмотрим этот алгоритм на примере.

Присвоим 1-й вершине метку равную 0, потому как эта вершина - источник. Остальным вершинам присвоим метки равные бесконечности.

Далее выберем такую вершину W, которая имеет минимальную метку (сейчас это вершина 1) и рассмотрим все вершины в которые из вершины W есть путь, не содержащий вершин посредников. Каждой из рассмотренных вершин назначим метку равную сумме метки W и длинны пути из W в рассматриваемую вершину, но только в том случае, если полученная сумма будет меньше предыдущего значения метки. Если же сумма не будет меньше, то оставляем предыдущую метку без изменений.

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

Мы выберем вершину 2. Но из нее нет ни одного исходящего пути, поэтому мы сразу отмечаем эту вершину как посещенную и переходим к следующей вершине с минимальной меткой. На этот раз только вершина 5 имеет минимальную метку. Рассмотрим все вершины в которые есть прямые пути из 5, но которые ещё не помечены как посещенные. Снова находим сумму метки вершины W и веса ребра из W в текущую вершину, и если эта сумма будет меньше предыдущей метки, то заменяем значение метки на полученную сумму.

Исходя из картинки мы можем увидеть, что метки 3-ей и 4-ой вершин стали меньше, тоесть был найден более короткий маршрут в эти вершины из вершины источника. Далее отмечаем 5-ю вершину как посещенную и выбираем следующую вершину, которая имеет минимальную метку. Повторяем все перечисленные выше действия до тех пор, пока есть непосещенные вершины.

Выполнив все действия получим такой результат:

Также есть вектор Р, исходя из которого можно построить кратчайшие маршруты. По количеству элементов этот вектор равен количеству вершин в графе, Каждый элемент содержит последнюю промежуточную вершину на кратчайшем пути между вершиной-источником и конечной вершиной. В начале алгоритма все элементы вектора Р равны вершине источнику (в нашем случае Р = {1, 1, 1, 1, 1}). Далее на этапе пересчета значения метки для рассматриваемой вершины, в случае если метка рассматриваемой вершины меняется на меньшую, в массив Р мы записываем значение текущей вершины W. Например: у 3-ей вершины была метка со значением «30», при W=1. Далее при W=5, метка 3-ей вершины изменилась на «20», следовательно мы запишем значение в вектор Р - Р=5. Также при W=5 изменилось значение метки у 4-й вершины (было «50», стало «40»), значит нужно присвоить 4-му элементу вектора Р значение W - P=5. В результате получим вектор Р = {1, 1, 5, 5, 1}.

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

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

Идея алгоритма следующая: сначала выберем путь до начальной вершины равным нулю и заносим эту вершину во множество уже выбранных, расстояние от которых до оставшихся невыбранных вершин определено. На каждом следующем этапе находим следующую выбранную вершину, расстояние до которой наименьшее, и соединенную ребром с какой-нибудь вершиной из множества невыбранных (это расстояние будет равно расстоянию до выбранной вершины плюс длина ребра).

Пример 1. Найти кратчайший путь на графе от вершины L до вершины D (рис. 10.7).

Рис. 10.7.

Запишем алгоритм в виде последовательности шагов (табл. 10.1). Шаг 1. Определяем расстояния от начальной вершины L до всех остальных.

Таблица 10.1

Метод Дейкстры (первый шаг)

Выбранная	Путь до выбранной вершины	Невыбранная вершина

Шаг 2. Выбираем наименьшее расстояние от L до В; найденная вершина В принимается за вновь выбранную. Найденное наименьшее расстояние добавляем к длинам ребер от новой вершины В до всех остальных. Выбираем минимальное расстояние от В до N. Новую вершину N принимаем за выбранную (табл. 10.2).

Таблица 10.2

Метод Дейкстры (второй шаг)

Выбранная	Путь до выбранной вершины	Невыбранная вершина

Для наглядности в дальнейшем вместо знака оо будем ставить знак « - ».

Шаг 3. Определяем расстояния от вершины N л о всех оставшихся (за исключением L и В), как показано в табл. 10.3.

Таблица 10.3

Метод Дейкстры (третий шаг)

Выбранная	Путь до выбранной вершины	Невыбранная вершина

Расстояние от вершины L через вершину N до вершины G равно 18 условных единиц. Это расстояние больше, чем расстояние LB + BG = 16 условных единиц, вследствие чего оно не учитывается в дальнейшем. Продолжая аналогичные построения, составим табл. 10.4. Таким образом, найдена длина кратчайшего пути между вершинами L и D (44 условных единицы).

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

Таблица 10.4

Выбранная вершина	Путь до выбранной вершины	Невыбранная вершина

В этом столбце минимальная длина, равная 27 условным единицам, указывает следующую вершину G, к которой надлежит перейти, и т.д. Таким образом, получаем траекторию пути: (L, В, G, S, D).

Пример 8. Найти кратчайший путь на графе между 1-й и 7-й вершинами (рис. 10.8).

Определяем (табл. 10.5) следующую выбранную вершину, расстояние до которой наименьшее и соединенную ребром с одной из вершин, принадлежащих множеству невыбранных (это расстояние будет равно расстоянию до выбранной вершины плюс длина ребра).

Рис. 10.8. Граф (а) и соответствующая ему матрица смежности (б)

Табличная реализация метода Дейкстры

Таблица 10.5

Выбранная	Путь до выбранной вершины	Невыбранная вершина
у 6

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

Просматриваем столбец, соответствующий вершине, снизу вверх и фиксируем первое появление минимальной величины. Кратчайший путь при этом будет равен (V 7 - V 5 - V 2 - У {).

и КОНТРОЛЬНЫЕ ВОПРОСЫ

• 1. Какова теоретическая сложность алгоритмов: построения дерева решений, динамического программирования и Дейкстры?
• 2. В чем особенность использования дерева решений для ориентированного и неорентированного графа?
• 3. В решении каких прикладных задач используются алгоритмы определения в графе кратчайших расстояний между заданными вершинами?
• 4. Может ли быть применен рассмотренный в работе алгоритм Дейкстры к определению кратчайшего расстояния в ориентированном графе?
• 5. Как работает алгоритм Дейкстры?
• 6. Как работает алгоритм динамического программирования применительно к задаче определения в графе кратчайших расстояний между вершинами?