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

Java   16 Август 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). В процессе работы алгоритма Дейкстры поддерживается множество S \subseteq V, состоящие из вершин v орграфа G, для которых кратчайшее расстояние dist[v] уже найдено. Булевский массив used служит для реализации множества S \subseteq V и хранения информации о том, найдено ли кратчайшее расстояние от стартовой вершины start до вершины v или еще нет. Массив pred служит для хранения предков и необходим для восстановления кратчайших путей из стартовой вершины start до всех остальных вершин v \in V орграфа G = (V, E).

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

В качестве списка смежности для представления графа на языке Java удобно использовать массив, каждый элемент которого является структурой данных ArrayList<Integer>.
В приведенной ниже реализации данные считываются и выводятся в консоль.

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

В первой строке входного файла задано два целых числа: 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
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();
    }
}

 

Пример
Входные данные
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:

 

  • Алексей

    Полезно, спасибо!
    Только с рекурсивной процедурой printWay не очень понятно. Как сохранить маршрут из стартовой вершины в какую-нибудь другую в массив например?

    • Алексей

      разобрался сам:)
      еще раз спасибо!

  • Олексій Моренець

    Зачем считывать из потока к-во вершин и ребер, когда их число можно подсчитать по мере считывания?

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

  • на Delphi

  • на Java

  • на C++