Advertisement
Lusien_Lashans

Dijkstra dijkstra

May 2nd, 2018
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.71 KB | None | 0 0
  1. package com.company;
  2. import java.util.*;
  3. import java.io.*;
  4.  
  5. public class Dijkstra {
  6.     private static int z, size = 6; // размер матрици 6х6
  7.     public static void dijkstra(Graph g, int s, long[] prio, int[] pred) {
  8.         try {  //считываем текст из ввода, буферизируя прочитанные символы
  9.             BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
  10.             System.out.print("Введите начальную точку: ");
  11.             String line = buf.readLine();
  12.             s = Integer.parseInt(line);
  13.             System.out.print("Введите конечную точку: ");
  14.             line = buf.readLine();
  15.             z = Integer.parseInt(line);
  16.             buf.close();
  17.         } catch (Exception e) {
  18.             System.exit(0);
  19.         }
  20.         Arrays.fill(pred, -1);
  21.         Arrays.fill(prio, INF);
  22.         prio[s] = 0;
  23.         Queue<QItem> q = new PriorityQueue<QItem>(); // устанавливаем приоритет размеров путей
  24.         q.add(new QItem(0, s));
  25.         while (!q.isEmpty()) {
  26.             QItem cur = q.poll();
  27.             if (cur.prio != prio[cur.v]) {
  28.                 continue;
  29.             }
  30.  
  31.             for (Edge e : g.nodeEdges[cur.v]) {
  32.                 long nprio = prio[cur.v] + e.cost;
  33.                 if (prio[e.t] > nprio) {
  34.                     prio[e.t] = nprio;
  35.                     pred[e.t] = cur.v;
  36.                     q.add(new QItem(nprio, e.t));
  37.                 }
  38.             }
  39.         }
  40.     }
  41.     public static int getZ(){return z;}
  42.     public static int getSize(){return size;}
  43.     public static final long INF = Long.MAX_VALUE / 10;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement