有向图最短路Dijkstras算法过程动态演示
浏览数：19 /
时间：2015年06月08日
/********************************************** 2015.1.9---1.12 by yzk ************************************************************************/
<pre name="code" class="java">import java.util.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.GeneralPath;
import java.lang.Thread;
import java.lang.Runnable;
public class init
{
public static void main(String[] args) throws Exception
{
//Graph g2=new Graph();
// login my=new login();
Graph g1=new Graph();
// Thread my=new Thread(g2);
// my.start();
//g1.gos();
// g2.start();
// g1.readin();
// g1.play();
//g1.setVisible(true);
}
}
import java.util.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.GeneralPath;
import java.lang.Thread;
import java.lang.Runnable;
public class Graph extends JFrame
{
public static int wait=0;
JButton stop= new JButton("STOP"); //暂停按钮
JButton go= new JButton("GO"); //开始按钮
public Graph ()throws Exception
{
setBounds(0, 0, 1380, 800); //设定大小
this.setBackground(Color.WHITE); //背景色
this.setTitle("基于OSPF协议的有向图最短路Dijkstra算法动态过程演示系统");
this.setLayout(null);
JLabel lblNewLabel = new JLabel("<html>最<br>短<br>路<br>算<br>法<br>动<br>态<br>过<br>程");
lblNewLabel.setFont(new Font("长城行楷体", Font.BOLD, 60)); //标签相关设置
lblNewLabel.setVerticalAlignment(SwingConstants.TOP); //置顶
lblNewLabel.setForeground(new Color(0, 0, 0));
lblNewLabel. setBounds(20,0,90,800);
add(lblNewLabel);
Gra temp=new Gra(); // 建图
temp.setBounds(90, 0, 1290, 800);
temp.readin();
add(temp);
this.setVisible(true);
temp.play(); //演示算法过程
}
}
class Gra extends JPanel
{
int [] head; //链式前向星存图
int [][] edge;
int nume;
int maxn; //顶点数
int maxm; //边数
int inf=0x3f3f3f3f; //无穷大
int ss,tt; //源汇点
int change; //开关量
int []mark; //最短路的标记
int []dis; //距离
int []got; //是否需要闪烁标记（正在被更新）
points [] dian; //点类
int [][] lines;
public Gra() //初始化构造函数
{
head=new int [1005];
edge=new int [5000][3];
lines= new int [10000][5];
dis=new int [1006];
got=new int [5000];
mark=new int [1006];
nume=0;
change=0;
for(int i=0;i<1000;i++)
{
head[i]=-1;dis[i]=inf;got[i]=mark[i]=0;
}
}
public void adde(int i,int j,int w) //添加一条有向边
{
edge[nume][0]=j;edge[nume][1]=head[i];head[i]=nume;
edge[nume++][2]=w;
}
void magic0() //延时重画函数
{
try {
Thread.sleep(300);
} catch (InterruptedException e) {
e.printStackTrace();
}
this.repaint();
}
void magic() //闪烁控制函数
{
int cur=5; //变换次数
while(cur!=0)
{
change=1; //灯开
magic0();
change=0; //灯灭
magic0();
cur--;
//System.out.println(cur);
}
}
public void readin ()throws Exception //读入图函数
{
java.io.File file= new java.io.File("scores.txt"); //读入数据
// java.io.File file= new java.io.File("scores2.txt"); //读入数据
// java.io.File file= new java.io.File("radscores.txt");
Scanner input =new Scanner(file);
while(input.hasNext())
{
maxn=input.nextInt();
maxm=input.nextInt();
int from,to,w;
for(int i=0;i<maxm;i++)
{
from=input.nextInt();
to=input.nextInt();
w=input.nextInt();
adde(from,to,w);
}
ss=input.nextInt(); tt=input.nextInt();
dis[ss]=0;
}
input.close();
java.io.File file2 = new java.io.File("points.txt"); //读入坐标点
// java.io.File file2 = new java.io.File("points2.txt");
//java.io.File file2= new java.io.File("radpoints.txt");
Scanner input2 =new Scanner(file2);
dian =new points [maxn+1];
for(int i=1;i<=maxn;i++)
{
dian[i]=new points(input2.nextInt(),input2.nextInt());
}
}
public void play() //Dijkstra算法
{
int marks=1;
while(marks==1)
{
int mins=inf;
marks=0;
int cur=0;
for(int i=1;i<=maxn;i++)
{
if(mark[i]==0&&dis[i]<mins)
{
mins=dis[i];
cur=i;
marks=1;
}
}
got[cur]=1; //点需要闪
magic();
got[cur]=0; //关闭该点，之后就不再闪
mark[cur]=1;
for(int j=head[cur];j!=-1;j=edge[j][1])
{
int to=edge[j][0];
if(mark[to]==0&&dis[to]>dis[cur]+edge[j][2])
{
dis[to]=dis[cur]+edge[j][2];
lines[j][0]=1; //该线已变色
lines[j][1]=1; //该线需要闪
magic();
lines[j][1]=0; //无需再闪
}
}
}
}
protected void paintComponent( Graphics g) //画图函数
{
super.paintComponent(g); //清屏
g.setColor(Color.green);
Font font = new Font("Arial", Font.BOLD, 25); //字体大小
g.setFont(font);
for(int i=1;i<=maxn;i++)
{
if(got[i]==1) //该点在闪
{
if(change==1) //灯开
g.setColor(Color.red);
else g.setColor(Color.GREEN); //灯灭
}
else
{
if(mark[i]==1) //该点已变
g.setColor(Color.red);
else g.setColor(Color.GREEN);
}
g.fillOval(dian[i].x, dian[i].y, 50, 50);
String ts;
if(dis[i]==inf)
ts="+∞";
else ts=new String().valueOf(dis[i]);
g.drawString(ts,dian[i].x,dian[i].y);
}
g.setColor(Color.GRAY);
for(int i=1;i<=maxn;i++)
{
for(int j=head[i];j!=-1;j=edge[j][1])
{
if(lines[j][1]==1) //需要闪烁
{
if(change==1)
g.setColor(Color.BLUE);
else g.setColor(Color.GRAY);
}
else
{
if(lines[j][0]==1) //已经变色
g.setColor(Color.BLUE);
else g.setColor(Color.GRAY);
}
// g.drawString(new String().valueOf(dis[edge[j][2]]),dian[i].x,dian[i].y);
Graphics2D g2= (Graphics2D)g;
drawAL(dian[i].x+25,dian[i].y+25, dian[edge[j][0]].x+25, dian[edge[j][0]].y+25,g2); //划边
// g.drawLine(dian[i].x+25,dian[i].y+25, dian[edge[j][0]].x+25, dian[edge[j][0]].y+25);
int mx=(dian[i].x+25+dian[edge[j][0]].x+25)/2;
int my=(dian[i].y+25+dian[edge[j][0]].y+25)/2;
g.drawString(new String().valueOf(edge[j][2]), mx,my);
}
}
}
public static void drawAL(int sx, int sy, int ex, int ey, Graphics2D g2)
{
double H = 20; // 箭头高度
double L = 6; // 底边的一半
int x3,y3,x4,y4;
double awrad = Math.atan(L / H); // 箭头角度
double arraow_len = Math.sqrt(L * L + H * H); // 箭头的长度
double[] arrXY_1 = rotateVec(ex - sx, ey - sy, awrad, true, arraow_len);
double[] arrXY_2 = rotateVec(ex - sx, ey - sy, -awrad, true, arraow_len);
double x_3 = ex - arrXY_1[0]; // (x3,y3)是第一端点
double y_3 = ey - arrXY_1[1];
double x_4 = ex - arrXY_2[0]; // (x4,y4)是第二端点
double y_4 = ey - arrXY_2[1];
Double X3 = new Double(x_3);
x3 = X3.intValue();
Double Y3 = new Double(y_3);
y3 = Y3.intValue();
Double X4 = new Double(x_4);
x4 = X4.intValue();
Double Y4 = new Double(y_4);
y4 = Y4.intValue();
g2.drawLine(sx, sy, ex, ey); // 画线
GeneralPath triangle = new GeneralPath();
triangle.moveTo(ex, ey);
triangle.lineTo(x3, y3);
triangle.lineTo(x4, y4);
triangle.closePath();
g2.fill(triangle); //实心箭头
//g2.draw(triangle); //非实心箭头
}
public static double[] rotateVec(int px, int py, double ang, // 计算箭头的左右俩的点
boolean isChLen, double newLen)
{
double mathstr[] = new double[2];
// 参数含义分别是x分量、y分量、旋转角、是否改变长度、新长度
double vx = px * Math.cos(ang) - py * Math.sin(ang);
double vy = px * Math.sin(ang) + py * Math.cos(ang);
if (isChLen) {
double d = Math.sqrt(vx * vx + vy * vy);
vx = vx / d * newLen;
vy = vy / d * newLen;
mathstr[0] = vx;
mathstr[1] = vy;
}
return mathstr;
}
}
class points
{
int x,y;
points(){};
points(int x,int y)
{
this.x=x;
this.y=y;
}
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
