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

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

Java

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

Статья
Комментарии (1)

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

Игорь

почему время его выполнения в порядок раз выше этой ? /algoritm-dejkstry-realizaciya-na-java.html

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

на Delphi
на Java
на C++

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

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

на Delphi

на Java

на C++