Алгоритм Дейкстры для разреженных графов (реализация на Java)

Java   23 августа 2015  Автор статьи:  
geekbrains.ru/

Задан ориентированный взвешенный граф G = (V, E), состоящий из N вершин и M дуг. Каждая дуга (u, v) имеет неотрицательный вес w(u, v), w(u, v) \ge 0. Требуется найти кратчайшие пути из некоторой стартовой вершины s до всех остальных вершин графа G.
Исходный граф G удобно представлять в памяти ЭВМ списком смежности adj, храня для каждой вершины графа v список adj[v] смежных с ней вершин. Для хранения весов дуг, соответствующих их положению в списке смежности adj, используется список смежности weight. Переменная start обозначает стартовую вершину, от которой ищется расстояние до всех других вершин v \in V. Массив dist используется для хранения текущего кратчайшего расстояния от стартовой вершины start до всех других вершин v \in V. Изначально полагаем, что dist[start] = 0, а для всех остальных вершин значение массива dist равно бесконечности INF. На практике при реализации алгоритмов в качестве бесконечности INF выбирают достаточное большое число, заведомо превосходящее длину любого пути в исходном орграфе G = (V, E). Массив pred служит для хранения предков и необходим для восстановления кратчайших путей из стартовой вершины start до всех остальных вершин v \in V орграфа G = (V, E).


ArrayList adj[]; //список смежности
ArrayList weight[]; //вес ребра в орграфе
boolean used[]; //массив для хранения информации о пройденных и не пройденных вершинах
int dist[]; //массив для хранения расстояния от стартовой вершины
int pred[]; //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины
Set queue = new TreeSet(); //очередь с приоритетами

В качестве списка смежности для представления графа на языке Java удобно использовать массив, каждый элемент которого является структурой данных ArrayList<Integer>. Для реализации очереди с приоритетами, в которые попадают вершины в порядке приближенности к стартовой вершине start, используется структура данных Set<Vertex>. Внутренний класс Vertex хранит пару значений v и weight, где v – номер вершины в орграфе G, а weight – текущее расстояние от стартовой вершины start до нее соответственно.
В приведенной ниже реализации данные считываются и выводятся в консоль.

Входные данные

В первой строке входного файла задано два целых числа: N (1 \le N \le 10^5) – количество вершин в графе, M (1 \le M \le 10^6) – количество ребер графа соответственно и стартовая вершина start (1 \le start \le N). Каждая из следующих M строк содержит описание дуги орграфа: три целых числа – начало, конец и вес дуги. Начало и конец дуги находятся в диапазоне от 1 до N, а вес ребра – это целое не отрицательно число.

Выходные данные

В первой строке выходного файла показано расстояние из стартовой вершины start до всех остальных вершин v \in V орграфа G = (V, E) в порядке их нумерации. Если пути из стартовой вершины start до некоторой вершины не существует, то на том месте стоит значение -1.
Далее в следующий N строках показан номер вершины и кратчайший путь до нее из стартовой вершины start. В случае, если пути до некоторой вершины v \in V не существует, то строка с номером v является пустой.


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.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

//класс, описывающий вершину и ее путь от стартовой,
//для реализации модифицированного алгоритма Дейкстры
class Vertex implements Comparable {
private int v; //номер вершины в орграфе
private int weight; //расстояние от стартовой вершины в вершине v

public int getV() {
return v;
}

public int getWeight() {
return weight;
}

//конструктор класса
public Vertex(int v, int weight) {
this.v = v;
this.weight = weight;
}

//метод для сравнения двух вершин по расстоянию до них
public int compareTo(Vertex vertex) {
if (weight != vertex.getWeight()) {
return Integer.compare(weight, vertex.getWeight());
}
return Integer.compare(v, vertex.getV());
}

@Override
public int hashCode() {
return weight * 57 + v;
}

@Override
public boolean equals(Object arg0) {
if (arg0 == null) {
return false;
}
if (this == arg0) {
return true;
}
Vertex vertex = (Vertex) arg0;
return v == vertex.getV() && weight == vertex.getWeight();
}
}

public class SparseDejkstra {

private static int INF = Integer.MAX_VALUE / 2;

private int n; //количество вершин в орграфе
private int m; //количествое дуг в орграфе
private ArrayList adj[]; //список смежности
private ArrayList weight[]; //вес ребра в орграфе
private int dist[]; //массив для хранения расстояния от стартовой вершины
private int pred[]; //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины
int start; //стартовая вершина, от которой ищется расстояние до всех других
Set queue = new TreeSet(); //очередь с приоритетами

private BufferedReader cin;
private PrintWriter cout;
private StringTokenizer tokenizer;

//процедура запуска алгоритма Дейкстры из стартовой вершины
private void sparseDejkstra(int s) {
dist[s] = 0; //кратчайшее расстояние до стартовой вершины равно 0
queue.add(new Vertex(s, dist[s]));
while (!queue.isEmpty()) {
//извлекаем вершину, которая находится вверху кучи
int v = queue.iterator().next().getV();
int distV = queue.iterator().next().getWeight();
queue.remove(queue.iterator().next());
//рассматриваем все дуги, исходящие из вершины вверху кучи
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]) { queue.remove(new Vertex(u, dist[u])); dist[u] = dist[v] + weightU; pred[u] = v; queue.add(new Vertex(u, dist[u])); } } } } //процедура считывания входных данных с консоли 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); } 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(); sparseDejkstra(start); printData(); cin.close(); cout.close(); } public static void main(String[] args) throws IOException { SparseDejkstra solution = new SparseDejkstra(); solution.run(); } }

 

Пример
Входные данные
7 11 1
1 2 1
1 3 7
2 4 4
2 5 2
3 2 4
3 5 5
4 5 3
5 3 3
5 4 10
6 7 3
7 6 4
Выходные данные
0 1 6 5 3 -1 -1
1: 1
2: 1 2
3: 1 2 5 3
4: 1 2 4
5: 1 2 5
6:
7:

 

Научиться программировать

  • на Delphi

  • на Java

  • на C++

geekbrains.ru/
geekbrains.ru/