Menor caminho

Programação Java
#1

boas,
Eu tenho um programa com arcos vértices e grafos , em que os arcos têm um certo peso e os vértices possuem uma linkedList que têm os arcos que têm como origem este vértice.
E depois tenho uma classe Graph com um vector de todos os vértices do grafo.

Eu preciso de fazer um algoritmo que determina a menor distância entre vértices.

Alguém já fez algo parecido que me possa dar algumas dicas ?

Eu encontrei uma coisa chamada algoritmo de Dijkstra mas n consigo perceber.

muito obrigado

#2

[quote=“saunde”]boas,
Eu tenho um programa com arcos vértices e grafos , em que os arcos têm um certo peso e os vértices possuem uma linkedList que têm os arcos que têm como origem este vértice.
E depois tenho uma classe Graph com um vector de todos os vértices do grafo.

Eu preciso de fazer um algoritmo que determina a menor distância entre vértices.

Alguém já fez algo parecido que me possa dar algumas dicas ?

Eu encontrei uma coisa chamada algoritmo de Dijkstra mas n consigo perceber.

muito obrigado[/quote]

Segue um exemplo de uma implementação do Dijkstra , é só " debugar ".

[code]
//
/* Dijkstra.java /
/ Copyright © 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) {}

}[/code]

Tem este aqui tbm que é muito interessante
:arrow: http://ict.udlap.mx/people/roberto/dijkstra/

Um abraço !

#3

Obrigado pela ajuda, mas n há nada mais simples ? Um site k explike o algoritmo… ou assim :S

#4

Posso olhar , guenta ae …
:arrow: http://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra
:arrow: http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/dijkstra.html

#5