Графы. Нахождение кратчайшего расстояния между двумя вершинами с помощью алгоритма Дейкстры
- Подробности
- Категория: Сортировка и поиск
Алгоритм Дейкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
Лекция 2: Алгоритмы и методы сортировки. Алгоритмы нахождения кратчайшего пути в графе
Лекция 5: Поиск в графах и обход. Алгоритм Дейкстры
Алгоритмы и структуры данных, лекция 13
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке.
Пусть требуется найти кратчайшие расстояния от 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++
#include "stdafx.h"
#include <iostream>
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<V; i++)
{
distance[i]=INT_MAX; visited[i]=false;
}
distance[st]=0;
for (count=0; count<V-1; count++)
{
int min=INT_MAX;
for (i=0; i<V; i++)
if (!visited[i] && distance[i]<=min)
{
min=distance[i]; index=i;
}
u=index;
visited[u]=true;
for (i=0; i<V; i++)
if (!visited[i] && GR[u][i] && distance[u]!=INT_MAX &&
distance[u]+GR[u][i]<distance[i])
distance[i]=distance[u]+GR[u][i];
}
cout<<"Стоимость пути из начальной вершины до остальных:\t\n";
for (i=0; i<V; i++) if (distance[i]!=INT_MAX)
cout<<m<<" > "<<i+1<<" = "<<distance[i]<<endl;
else cout<<m<<" > "<<i+1<<" = "<<"маршрут недоступен"<<endl;
}
//главная функция
void main()
{
setlocale(LC_ALL, "Rus");
int start, GR[V][V]={
{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}};
cout<<"Начальная вершина >> "; cin>>start;
Dijkstra(GR, start-1);
system("pause>>void");
}
Pascal
program DijkstraAlgorithm;
uses crt;
const V=6; inf=100000;
type vektor=array[1..V] of integer;
var start: integer;
const GR: array[1..V, 1..V] 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[1..V, 1..V] of integer; st: integer);
var count, index, i, u, m, min: integer;
distance: vektor;
visited: array[1..V] of boolean;
begin
m:=st;
for i:=1 to V do
begin
distance[i]:=inf; visited[i]:=false;
end;
distance[st]:=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[u, i]<>0) and (distance[u]<>inf) and
(distance[u]+GR[u, i]<distance[i]) then
distance[i]:=distance[u]+GR[u, i];
end;
write('Стоимость пути из начальной вершины до остальных:'); writeln;
for i:=1 to V do
if distance[i]<>inf 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<Integer> adj[]; //список смежности
private ArrayList<Integer> 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<Integer>();
}
//инициализация списка, в котором хранятся веса ребер
weight = new ArrayList[n];
for (int i = 0; i < n; ++i) {
weight[i] = new ArrayList<Integer>();
}
//считываем граф, заданный списком ребер
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<String, Vertex> 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<Vertex> {
public final String name;
public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
public Vertex previous = null;
public final Map<Vertex, Integer> 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<Vertex> 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<Vertex> 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<Vertex, Integer> 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
//#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[8]; /* 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[BLOCK_SIZE].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[BLOCK_SIZE].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[j = i/2]->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[1];
tmp = heap[heap_len--];
for (i = 1; i < heap_len && (j = i * 2) <= heap_len; i = j) {
if (j < heap_len && heap[j]->dist > heap[j+1]->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
<?php
function dijkstra($graph_array, $source, $target) {
$vertices = array();
$neighbours = array();
foreach ($graph_array as $edge) {
array_push($vertices, $edge[0], $edge[1]);
$neighbours[$edge[0]][] = array("end" => $edge[1], "cost" => $edge[2]);
$neighbours[$edge[1]][] = array("end" => $edge[0], "cost" => $edge[2]);
}
$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";
Output is:
path is: a, c, f, e
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 = [Edge(*edge) for edge in edges]
self.vertices = set(sum(([e.start, e.end] 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[source] = 0
q = self.vertices.copy()
neighbours = {vertex: set() for vertex in self.vertices}
for start, end, cost in self.edges:
neighbours[start].add((end, cost))
#pp(neighbours)
while q:
u = min(q, key=lambda vertex: dist[vertex])
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']
