Алгоритм Дейкстры для разреженных графов (реализация на Java)
Задан ориентированный взвешенный граф , состоящий из
вершин и
дуг. Каждая дуга
имеет неотрицательный вес
,
. Требуется найти кратчайшие пути из некоторой стартовой вершины
до всех остальных вершин графа
.
Исходный граф удобно представлять в памяти ЭВМ списком смежности
, храня для каждой вершины графа
список
смежных с ней вершин. Для хранения весов дуг, соответствующих их положению в списке смежности
, используется список смежности
. Переменная
обозначает стартовую вершину, от которой ищется расстояние до всех других вершин
. Массив
используется для хранения текущего кратчайшего расстояния от стартовой вершины
до всех других вершин
. Изначально полагаем, что
, а для всех остальных вершин значение массива
равно бесконечности
. На практике при реализации алгоритмов в качестве бесконечности
выбирают достаточное большое число, заведомо превосходящее длину любого пути в исходном орграфе
. Массив
служит для хранения предков и необходим для восстановления кратчайших путей из стартовой вершины
до всех остальных вершин
орграфа
.
ArrayList
ArrayList
boolean used[]; //массив для хранения информации о пройденных и не пройденных вершинах
int dist[]; //массив для хранения расстояния от стартовой вершины
int pred[]; //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины
Set
В качестве списка смежности для представления графа на языке 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.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
private ArrayList
private int dist[]; //массив для хранения расстояния от стартовой вершины
private int pred[]; //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины
int start; //стартовая вершина, от которой ищется расстояние до всех других
Set
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: |
-
Игорь