dijkstra.java

Dijkstra算法在JAVA中的实现方法

/********************************************/ 
/* Dijkstra.java                            */ 
/* Copyright (C) 1997, 1998, 2000  K. Ikeda */ 
/********************************************/ 

import java.applet.*; 
import java.awt.*; 
import java.awt.event.*; 
import java.util.*; 
import java.io.*; 
import java.net.URL; 

class Node { 
　　　int　　　x; 
　　　int　　　y; 
　　　int　　　delta_plus;　　　/* edge starts from this node */ 
　　　int　　　delta_minus;　　　/* edge terminates at this node */ 
　　　int　　　dist;　　　　　　/* distance from the start node */ 
　　　int　　　prev;　　　　　　/* previous node of the shortest path */ 
　　　int　　　succ,pred;　　　/* node in Sbar with finite dist. */ 
　　　int　　　w; 
　　　int　　　h; 
　　　int　　　pw; 
　　　int　　　dx; 
　　　int　　　dy; 
　　　String　　　name; 
} 

class Edge { 
　　　int　　　rndd_plus;　　　/* initial vertex of this edge */ 
　　　int　　　rndd_minus;　　　/* terminal vertex of this edge */ 
　　　int　　　delta_plus;　　　/* edge starts from rndd_plus */ 
　　　int　　　delta_minus;　　　/* edge terminates at rndd_minus */ 
　　　int　　　len;　　　　　　/* length */ 
　　　String　　　name; 
} 

public class Dijkstra extends Applet implements MouseListener { 
　　　int　　　n,m; 
　　　int　　　u,snode;　　　/* start node */ 
　　　int　　　pre_s_first, pre_s_last; 
　　　boolean　　　isdigraph; 
　　　int　　　iteration, step; 
　　　Node　　　v[] = new Node[100]; 
　　　Edge　　　e[] = new Edge[200]; 

　　　int findNode(String name) { 
　　　　　　for (int i=0; i 　　　　　　　　　if (v.name.equals(name)) 
　　　　　　　　　　　　return i; 
　　　　　　return -1; 
　　　} 

　　　void input_graph(InputStream is) throws IOException { 
　　　　　　int x,y,l; 
　　　　　　String　　　s; 

　　　　　　Reader r = new BufferedReader(new InputStreamReader(is)); 
　　　　　　StreamTokenizer st = new StreamTokenizer(r); 
　　　　　　st.commentChar('#'); 
　　　　　　st.nextToken();　　　n = (int)st.nval; 
　　　　　　st.nextToken();　　　m = (int)st.nval; 
　　　　　　st.nextToken();　　　s = st.sval; 
　　　　　　isdigraph = "digraph".equals(s); 
　　　　　　for (int i = 0; i 　　　　　　　　　Node node = new Node(); 
　　　　　　　　　st.nextToken();　　　node.name = st.sval; 
　　　　　　　　　st.nextToken();　　　node.x = (int)st.nval; 
　　　　　　　　　st.nextToken();　　　node.y = (int)st.nval; 
　　　　　　　　　v = node; 
　　　　　　} 
　　　　　　for (int i = 0; i 　　　　　　　　　Edge edge = new Edge(); 
　　　　　　　　　st.nextToken();　　　edge.name = st.sval; 
　　　　　　　　　switch (st.nextToken()) { 
　　　　　　　　　case StreamTokenizer.TT_NUMBER: 
　　　　　　　　　　　　edge.rndd_plus = (int)st.nval; 
　　　　　　　　　　　　break; 
　　　　　　　　　case StreamTokenizer.TT_WORD: 
　　　　　　　　　　　　edge.rndd_plus = findNode(st.sval); 
　　　　　　　　　　　　break; 
　　　　　　　　　default: 
　　　　　　　　　　　　break; 
　　　　　　　　　} 
　　　　　　　　　switch (st.nextToken()) { 
　　　　　　　　　case StreamTokenizer.TT_NUMBER: 
　　　　　　　　　　　　edge.rndd_minus = (int)st.nval; 
　　　　　　　　　　　　break; 
　　　　　　　　　case StreamTokenizer.TT_WORD: 
　　　　　　　　　　　　edge.rndd_minus = findNode(st.sval); 
　　　　　　　　　　　　break; 
　　　　　　　　　default: 
　　　　　　　　　　　　break; 
　　　　　　　　　} 
　　　　　　　　　st.nextToken();　　　edge.len = (int)st.nval; 
　　　　　　　　　e = edge; 
　　　　　　} 
　　　　　　for (int i=0; i 　　　　　　　　　v.succ = v.pred = -2; 
　　　　　　　　　v.prev = v.dist = -1; 
　　　　　　　　　v.pw = 0; 
　　　　　　} 
　　　　　　iteration = step = 0; 
　　　} 

　　　void rdb() { 
　　　　　　int　　　i,k; 

　　　　　　for (i=0; i 　　　　　　　　　v.delta_plus = v.delta_minus = -1; 
　　　　　　for (i=0; i 　　　　　　　　　e.delta_plus = e.delta_minus = -1; 
　　　　　　for (i=0; i 　　　　　　　　　k = e.rndd_plus; 
　　　　　　　　　if (v[k].delta_plus == -1) 
　　　　　　　　　　　　v[k].delta_plus = i; 
　　　　　　　　　else { 
　　　　　　　　　　　　k = v[k].delta_plus; 
　　　　　　　　　　　　while(e[k].delta_plus >= 0) 
　　　　　　　　　　　　　　　k = e[k].delta_plus; 
　　　　　　　　　　　　e[k].delta_plus = i; 
　　　　　　　　　} 
　　　　　　　　　k = e.rndd_minus; 
　　　　　　　　　if (v[k].delta_minus == -1) 
　　　　　　　　　　　　v[k].delta_minus = i; 
　　　　　　　　　else { 
　　　　　　　　　　　　k = v[k].delta_minus; 
　　　　　　　　　　　　while(e[k].delta_minus >= 0) 
　　　　　　　　　　　　　　　k = e[k].delta_minus; 
　　　　　　　　　　　　e[k].delta_minus = i; 
　　　　　　　　　} 
　　　　　　} 
　　　} 

　　　void append_pre_s(int i) { 
　　　　　　v.succ = v.pred = -1; 
　　　　　　if (pre_s_first<0) 
　　　　　　　　　pre_s_first = i; 
　　　　　　else 
　　　　　　　　　v[pre_s_last].succ = i; 
　　　　　　v.pred = pre_s_last; 
　　　　　　pre_s_last = i; 
　　　} 

　　　void remove_pre_s(int i) { 
　　　　　　int　　　succ = v.succ; 
　　　　　　int　　　pred = v.pred; 

　　　　　　if (succ>=0) 
　　　　　　　　　v[succ].pred = pred; 
　　　　　　else 
　　　　　　　　　pre_s_last = pred; 
　　　　　　if (pred>=0) 
　　　　　　　　　v[pred].succ = succ; 
　　　　　　else 
　　　　　　　　　pre_s_first = succ; 
　　　} 

　　　void step1() {　　　　　　/* initialize */ 
　　　　　　u = snode; 
　　　　　　for (int i=0; i 　　　　　　　　　v.succ = v.pred = -2; 
　　　　　　　　　v.prev = v.dist = -1; 
　　　　　　} 
　　　　　　v.succ = -3; 
　　　　　　v.dist = 0; 
　　　　　　pre_s_first = pre_s_last = -1; 
　　　} 

　　　void step2() {　　　　　　/* replace labels */ 
　　　　　　int i,j; 

　　　　　　j = v.delta_plus; 
　　　　　　while (j>=0) { 
　　　　　　　　　i = e[j].rndd_minus; 
　　　　　　　　　if ((v.succ>=-2)&&((v.dist<0)││ 
　　　　　　　　　　　　(v.dist>v.dist+e[j].len))) { 
　　　　　　　　　　　　if (v.dist<0) 
　　　　　　　　　　　　　　　append_pre_s(i); 
　　　　　　　　　　　　v.dist = v.dist + e[j].len; 
　　　　　　　　　　　　v.prev = u;　　　  /* label */ 
　　　　　　　　　} 
　　　　　　　　　j = e[j].delta_plus; 
　　　　　　} 
　　　　　　if (!isdigraph) { 
　　　　　　j = v.delta_minus; 
　　　　　　while (j>=0) { 
　　　　　　　　　i = e[j].rndd_plus; 
　　　　　　　　　if ((v.succ>=-2)&&((v.dist<0)││ 
　　　　　　　　　　　　(v.dist>v.dist+e[j].len))) { 
　　　　　　　　　　　　if (v.dist<0) 
　　　　　　　　　　　　　　　append_pre_s(i); 
　　　　　　　　　　　　v.dist = v.dist + e[j].len; 
　　　　　　　　　　　　v.prev = u;　　　  /* label */ 
　　　　　　　　　} 
　　　　　　　　　j = e[j].delta_minus; 
　　　　　　} 
　　　　　　} 
　　　　　　v.succ = -4; 
　　　} 

　　　void step3() {　　　　　　/* find the shortest node in Sbar */ 
　　　　　　int i,rho; 

　　　　　　rho = -1; 
　　　　　　for (i = pre_s_first; i>=0; i = v.succ) { 
　　　　　　　　　if ((rho < 0)││(rho>v.dist)) { 
　　　　　　　　　　　　rho = v.dist; 
　　　　　　　　　　　　u = i; 
　　　　　　　　　} 
　　　　　　} 
　　　　　　remove_pre_s(u); 
　　　　　　v.succ = -3; 
　　　} 

　　　void step4() { 
　　　　　　v.succ = -4; 
　　　} 

　　　double weight(Node n, double x, double y) { 
　　　　　　double　　　w,z,xx,yy; 

　　　　　　w = 0; 
　　　　　　for (int j = n.delta_plus; j>=0; j=e[j].delta_plus) {