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

Java   23 Август 2015  Автор статьи:  

Задан ориентированный взвешенный граф 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).

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

В качестве списка смежности для представления графа на языке 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 является пустой.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
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<Vertex> {
    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<Integer> adj[]; //список смежности
    private ArrayList<Integer> weight[]; //вес ребра в орграфе
    private int dist[]; //массив для хранения расстояния от стартовой вершины
    private int pred[]; //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины   
    int start; //стартовая вершина, от которой ищется расстояние до всех других
    Set<Vertex> queue = new TreeSet<Vertex>(); //очередь с приоритетами
   
    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<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);
        }
       
        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++