dijkstra.java

用java实现的最短路径dijkstra算法

/********************************************/
/* 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<n; i++)
			if (v[i].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<n; 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[i] = node;
		}
		for (int i = 0; i<m; 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[i] = edge;
		}
		for (int i=0; i<n; i++) {
			v[i].succ = v[i].pred = -2;
			v[i].prev = v[i].dist = -1;
			v[i].pw = 0;
		}
		iteration = step = 0;
	}

	void rdb() {
		int	i,k;

		for (i=0; i<n; i++)
			v[i].delta_plus = v[i].delta_minus = -1;
		for (i=0; i<m; i++)
			e[i].delta_plus = e[i].delta_minus = -1;
		for (i=0; i<m; i++) {
			k = e[i].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[i].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[i].succ = v[i].pred = -1;
		if (pre_s_first<0)
			pre_s_first = i;
		else
			v[pre_s_last].succ = i;
		v[i].pred = pre_s_last;
		pre_s_last = i;
	}

	void remove_pre_s(int i) {
		int	succ = v[i].succ;
		int	pred = v[i].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<n; i++) {
			v[i].succ = v[i].pred = -2;
			v[i].prev = v[i].dist = -1;
		}
		v[u].succ = -3;
		v[u].dist = 0;
		pre_s_first = pre_s_last = -1;
	}

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

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

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

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

	void step4() {
		v[u].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) {
			xx = (double)(v[e[j].rndd_minus].x - n.x);
			yy = (double)(v[e[j].rndd_minus].y - n.y);
			z = (x*xx+y*yy)/Math.sqrt((x*x+y*y)*(xx*xx+yy*yy))+1.0;
			w += z*z*z*z;
		}
		for (int j = n.delta_minus; j>=0; j=e[j].delta_minus) {
			xx = (double)(v[e[j].rndd_plus].x - n.x);
			yy = (double)(v[e[j].rndd_plus].y - n.y);
			z = (x*xx+y*yy)/Math.sqrt((x*x+y*y)*(xx*xx+yy*yy))+1.0;
			w += z*z*z*z;
		}
		return w;
	}

	void init_sub() {
		int x[] = {1, 0, -1, 1, 0, -1};
		int y[] = {1, 1, 1, -1, -1, -1};
		int 	i,j,k;
		double	w,z;

		for (i=0; i<n; i++) {
			k=0;
			w=weight(v[i],(double)x[0],(double)y[0]);
			for (j=1; j<6; j++) {
				z=weight(v[i],(double)x[j],(double)y[j]);
				if (z<w) {
					w = z;
					k = j;
				}
			}
			v[i].dx = x[k];
			v[i].dy = y[k];
		}
	}

	public void init() {
		String mdname = getParameter("inputfile");
		try {
			InputStream is;

			is = new URL(getDocumentBase(),mdname).openStream();
			input_graph(is);
			try {
				if (is != null)
					is.close();
				} catch(Exception e) {
			}
		} catch (FileNotFoundException e) {
			System.err.println("File not found.");
		} catch (IOException e) {
			System.err.println("Cannot access file.");
		}

		String s = getParameter("start");
		if (s != null)
			snode = Integer.parseInt(s);
		else
			snode = 0;

		setBackground(Color.white);
		rdb();
		init_sub();
		addMouseListener(this);
	}

	public void paintNode(Graphics g, Node n, FontMetrics fm) {
		String s;
		int x = n.x;
		int y = n.y;
		int w = fm.stringWidth(n.name) + 10;
		int h = fm.getHeight() + 4;
		n.w = w;
		n.h = h;

		if (n.succ<-2)
			g.setColor(Color.blue);
		else if (n.succ==-2)
			g.setColor(Color.gray);
		else
			g.setColor(Color.red);

		g.drawRect(x-w/2,y-h/2,w,h);

		if (n.succ==-4)
			g.setColor(Color.cyan);
		else if (n.succ==-3)
			g.setColor(Color.pink);
		else if (n.succ>-2)
			g.setColor(Color.yellow);
		else
			g.setColor(getBackground());

		g.fillRect(x-w/2+1,y-h/2+1,w-1,h-1);

		g.setColor(Color.black);
		g.drawString(n.name,x-(w-10)/2,(y-(h-4)/2)+fm.getAscent());


		if (n.dist<0)
			s = "";
		else
			s = ""+n.dist;
		w = fm.stringWidth(s) + 10;
		x += (h+1)*n.dx; y += (h+1)*n.dy;
		g.setColor(getBackground());
		g.fillRect(x-n.pw/2,y-h/2,n.pw,h);
		n.pw = w;
		if (n.succ<-2)
			g.setColor(Color.blue);
		else
			g.setColor(Color.red);
		g.drawString(s,x-(w-10)/2,y-(h-4)/2+fm.getAscent());
	}

	int [] xy(int a, int b, int w, int h) {
		int	x[] = new int[2];

		if (Math.abs(w*b)>=Math.abs(h*a)) {
			x[0] = ((b>=0)?1:-1)*a*h/b/2;
			x[1] = ((b>=0)?1:-1)*h/2;
		} else {
			x[0] = ((a>=0)?1:-1)*w/2;
			x[1] = ((a>=0)?1:-1)*b*w/a/2;
		}
		return x;
	}

	void drawArrow(Graphics g,int x1,int y1,int x2,int y2) {
		int	a = x1-x2;
		int	b = y1-y2;

		if (isdigraph) {
		double	aa = Math.sqrt(a*a+b*b)/16.0;
		double	bb = b/aa;
			aa = a/aa;
		g.drawLine(x2,y2,x2+(int)((aa*12+bb*5)/13),y2+(int)((-aa*5+bb*12)/13));
		g.drawLine(x2,y2,x2+(int)((aa*12-bb*5)/13),y2+(int)((aa*5+bb*12)/13));
		}
		g.drawLine(x1,y1,x2,y2);
	}

	public void paintEdge(Graphics g, Edge e, FontMetrics fm) {
		Node v1 = v[e.rndd_plus];
		Node v2 = v[e.rndd_minus];

		int a = v1.x-v2.x;
		int b = v1.y-v2.y;

		int x1[] = xy(-a,-b,v1.w,v1.h);
		int x2[] = xy(a,b,v2.w,v2.h);

		if (v2.prev == e.rndd_plus) {
			if ((v1.succ<-2)&&(v2.succ>=-2))
				g.setColor(Color.red);
			else
				g.setColor(Color.blue);
		} else {
			g.setColor(Color.lightGray);
		}
		if ((!isdigraph)&&(v1.prev == e.rndd_minus)) {
			if ((v2.succ<-2)&&(v1.succ>=-2))
				g.setColor(Color.red);
			else
				g.setColor(Color.blue);
		}
		drawArrow(g,v1.x+x1[0],v1.y+x1[1],v2.x+x2[0],v2.y+x2[1]);

		int w = fm.stringWidth("" + e.len);
		int h = fm.getHeight();

		g.setColor(getBackground());
		g.fillRect((v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2,w,h);

		if ((v2.prev == e.rndd_plus)||
		    ((!isdigraph)&&(v1.prev == e.rndd_minus)))
			g.setColor(Color.black);
		else
			g.setColor(Color.lightGray);
		g.drawString("" + e.len,(v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2+fm.getAscent());
	}

	public void paint(Graphics g) {
		FontMetrics fm = g.getFontMetrics();
		for (int i=0; i<n; i++)
			paintNode(g,v[i],fm);
		for (int i=0; i<m; i++)
			paintEdge(g,e[i],fm);
	}

	public void update(Graphics g) {
		paint(g);
	}

	public void mousePressed(MouseEvent ev) {
		if (iteration==0) {
			step1();
			iteration++;
			step = 2;
		} else if (iteration>=n) {
			step4();
			iteration = 0;
		} else {
			if (step == 2) {
				step2();
				step = 3;
			} else {
				step3();
				iteration++;
				step = 2;
			}
		}
		repaint();
	}
	public void mouseClicked(MouseEvent event) {}
	public void mouseReleased(MouseEvent event) {}
	public void mouseEntered(MouseEvent event) {}
	public void mouseExited(MouseEvent event) {}
}