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

9, 99, 99, 14},
{7, 0, 10, 15, 99, 99},
{9, 10, 0, 11, 99, 2},
{99, 15, 11, 0, 6, 99},
{99, 99, 99, 6, 0, 9},
{14, 99, 2, 99, 9, 0}
};

static class QItem implements Comparable {
long prio; int v;
public QItem(long prio, int v) { this.prio = prio; this.v = v; }
public int compareTo(QItem q) { return prio < q.prio ? -1 : prio > q.prio ? 1 : 0; } },




public static class Edge {
public int s, t, cost;
public Edge(int s, int t, int cost) { this.s = s; this.t = t; this.cost = cost; } }

public static class Graph {
public final int n;
public List[] nodeEdges;
public Graph(int n) {
this.n = n;
nodeEdges = new List[n];
for (int i = 0; i < n; i++) { nodeEdges[i] = new ArrayList(); } }
void addEdge(int s, int t, int cost) {
nodeEdges[s].add(new Edge(s, t, cost)); } }

Реализация Классов

В интерфейсе Comparable объявлен всего один метод compareTo(Object obj), предназначенный для реализации упорядочивания объектов класса. Его удобно использовать при сортировке упорядоченных списков или массивов объектов. Данный метод сравнивает вызываемый объект с obj. compareTo возвращает:·         0, если значения равны;         Отрицательное значение, если вызываемый объект меньше параметра;        Положительное значение ,  если вызываемый объект больше параметра.

= arr.length;
Graph g = new Graph(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] != 0) {
g.addEdge(i, j, arr[i][j]);
}
}
}
long[] path = new long[g.n];
int[] pred = new int[g.n];
dijkstra(g, 0, path, pred);
System.out.println("Shortest path: "+path[z]);
printPath(pred, z); }

public static void dijkstra(Graph g, int s, long[] prio, int[] pred) {
private static int z, size = 6;
public static void dijkstra(Graph g, int s, long[] prio, int[] pred) {
try{ BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter an initial top: ");
String line = buf.readLine(); s = Integer.parseInt(line);
System.out.print("Enter an eventual top: ");
line = buf.readLine(); z = Integer.parseInt(line); buf.close(); }
catch(Exception e) { System.err.println(e.toString()); System.exit(0); }

pred) {
private static int z, size = 6;
public static void dijkstra(Graph g, int s, long[] prio, int[] pred) {
try{ BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter an initial top: ");
String line = buf.readLine(); s = Integer.parseInt(line);
System.out.print("Enter an eventual top: ");
line = buf.readLine(); z = Integer.parseInt(line); buf.close(); }
catch(Exception e) { System.err.println(e.toString()); System.exit(0); }


Arrays.fill(pred, -1); Arrays.fill(prio, INF); prio[s] = 0;
Queue q = new PriorityQueue();
q.add(new QItem(0, s));
while (!q.isEmpty()) { QItem cur = q.poll();
if (cur.prio != prio[cur.v]) { continue; }
for (Edge e : g.nodeEdges[cur.v])
{long nprio = prio[cur.v] + e.cost;
if (prio[e.t] > nprio)
{ prio[e.t] = nprio;
pred[e.t] = cur.v;
q.add(new QItem(nprio, e.t)); }
} } }

пары (ключ, значение) и достаточно быстро выполнять две операции:
вставка элемента с назначенным приоритетом;
извлечение элемента с наивысшим приоритетом;

Queue q = new PriorityQueue();