基于迪克斯特拉(Dijkstra)算法的物流优化系统（Java语言）
作者 郭世龙
算法介绍
Dijkstra算法是由荷兰计算机科学家艾兹格·迪克斯特拉发现的。算法解决的是有向图中最短路径问题。举例来说，如果图中的顶点表示配送点，而边上的权重表示各配送点间开车行经的距离。 Dijkstra算法可以用来找到两个配送点之间的最短路径。Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。 因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。
Dijkstra算法是由荷兰计算机科学家艾兹格·迪克斯特拉发现的。算法解决的是有向图中最短路径问题。举例来说，如果图中的顶点表示配送点，而边上的权重表示各配送点间开车行经的距离。 Dijkstra算法可以用来找到两个配送点之间的最短路径。Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。 因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。
基本思想是：设置一个顶点的集合s，并不断地扩充这个集合，一个顶点属于集合s当且仅当从源点到该点的路径已求出。开始时s中仅有源点，并且调整非s中点的最短路径长度，找当前最短路径点，将其加入到集合s，直到终点在s中。具体的算法过程可以参考图论的书籍。
系统介绍
系统以武汉市为例，自定义了一些配点作为定点，提取了可行道路作为边，并且自定义了边之间的权重，权重这里代表行驶时间。如图1，图2。系统实现了求任意两点之间的最短路径如图3。作为附加功能，实现了屏幕截取优化图以及打印优化图的功能。
图1 武汉市地图
图2 抽象出来的点和边
图3 最优路径图
程序解析
在系统实现的程序中共声明了六个类：主框架类Logistics，该类继承了JFrame类，用作绘图面板、文本框、菜单的容器及事件响应；绘图面板类computermap，该类继承了JPanel类，用作坐标系的绘制、图的绘制；打印类printer，该类实现了Printable接口，用来实现地图的打印功能；Dijkstra类和MinShortPath类 用来实现迪克斯特拉算法；Side类用来实现对边的操作。
绘图功能是通过computermap类来现。该类继承于JPanel类，JPanel用作绘图面板。JPanel类中的PaintCompenent（）函数用来负责绘制组件，该函数在必要的时候会自动调用，比如第一次启动程序、面板大小或位置被调整、有新组件加入面板等。程序不能直接调用PaintCompenent（）函数，否则会引起喷绘系统的混乱，但是可调用repaint（）函数来实现组件的重绘，repaint（）函数将在恰当的时候调用PaintCompenet（）函数。
程序中最可能覆盖的方法是PaintCompenent（），它是组件重绘自身的三个方法中的一个。这三个方法以下面的顺序发生：
paintComponent——绘制的主要方法。默认情况下，它首先绘制背景，然后绘制程序定制的图形。
paintBorder——绘制组件的边框。不能直接调用或覆盖该方法。
paintChildren—— 通知组件重绘自身来重绘子组件。不能直接调用或覆盖该方法。
程序通过覆盖paintComponent（）方法来实现绘图功能。首先在paintComponent（）调用超类的paintComponent（）函数实现超类中超类函数的功能，然后定制将要绘制的图形。
代码：
public void paintComponent(Graphics ge)
{
Graphics2D g=(Graphics2D) ge;
super.paintComponent(g); //显示白色，如果没有super则显示灰色
panelSize = getSize();
RectPoint=this.getLocation();//getLocation()获得当前组件的屏幕坐标
//g.setColor(Color.gray);
g.setColor(Color.green);
//绘制X、Y轴
g.drawLine(10,panelSize.height-10,10,0);
g.drawLine(10,panelSize.height-10,panelSize.width,panelSize.height-10);
g.drawString("0",3,panelSize.height-2);
g.drawString(new Integer((int)(panelSize.height/10)).toString(),20,20);
g.drawString(new Integer((int)(panelSize.width/10)).toString(),panelSize.width-30,panelSize.height-20);
//绘制Y轴箭头
g.drawLine(panelSize.width,panelSize.height-10,panelSize.width-10,panelSize.height-5);
g.drawLine(panelSize.width,panelSize.height-10,panelSize.width-10,panelSize.height-15);
//绘制X轴箭头
g.drawLine(10,0,5,5);
g.drawLine(10,0,15,5);
//绘制刻度
//绘制Y轴刻度
int isomerous1 = panelSize.width/10;
for(int j = 0;j<isomerous1 ;j++)
{
g.drawLine(j*10,panelSize.height-10,j*10,panelSize.height-15);
}
//绘制X轴刻度
int isomerous2 =panelSize.height/10;
for(int j = 0;j<isomerous2 ;j++)
{
g.drawLine(10,panelSize.height-j*10,15,panelSize.height-j*10);
}
//to draw Logistics map Sides
for(Side iterator : mapSide)
{
float mapPointX1=30+(ArryListLine.get(iterator.getNode()-1).x )* panelSize.width/12;
float mapPointY1=30+(ArryListLine.get(iterator.getNode()-1).y )* panelSize.height/9;
float mapPointX2=30+(ArryListLine.get(iterator.getPreNode()-1).x )* panelSize.width/12;
float mapPointY2=30+(ArryListLine.get(iterator.getPreNode()-1).y )* panelSize.height/9;
int X1=(int)mapPointX1; int Y1=(int) mapPointY1;
int X2=(int)mapPointX2; int Y2=(int) mapPointY2;
Color colorCurrent=g.getColor();
g.setColor(Color.orange);
g.setStroke(new BasicStroke(2.0f));
g.drawOval(X1-2,Y1-2, 6, 6);
g.drawString(new Integer(mapSide.get(0).getPreNode()).toString(), (int)(0.4*panelSize.width/12+30-5),(int)(1.0*panelSize.height/9+30-5));
g.drawString(new Integer( iterator.getNode()).toString(),X1-5,Y1-5);
g.drawOval(X2-2,Y2-2, 6, 6);
g.setStroke(new BasicStroke());
g.setColor(Color.gray);
g.drawLine(X1,Y1,X2,Y2);
g.setColor(colorCurrent);
//to draw the minishort path ,the elements of ArryListOptLine are added into ArryListOptLine in Dijkatra class.
for(int i=0;i<ArryListOptLine.size()-1;i++)
{
g.setColor(Color.blue);
g.setStroke(new BasicStroke(0.5f));
float PointX1=0+(ArryListLine.get(ArryListOptLine.get(0)-1).x)* panelSize.width/12;
float PointY1=0+(ArryListLine.get(ArryListOptLine.get(0)-1).y)* panelSize.height/9;
float PointX2=60+(ArryListLine.get(ArryListOptLine.get(ArryListOptLine.size()-1)-1).x )* panelSize.width/12;
float PointY2=150+(ArryListLine.get(ArryListOptLine.get(ArryListOptLine.size()-1)-1).y )* panelSize.height/9;
g.drawRect((int)PointX1,(int)PointY1,((int)PointX2-(int)PointX1),((int)PointY2-(int)PointY1) );
float OptmapPointX1=30+(ArryListLine.get(ArryListOptLine.get(i)-1).x)* panelSize.width/12;
float OptmapPointY1=30+(ArryListLine.get(ArryListOptLine.get(i)-1).y)* panelSize.height/9;
float OptmapPointX2=30+(ArryListLine.get(ArryListOptLine.get(i+1)-1).x )* panelSize.width/12;
float OptmapPointY2=30+(ArryListLine.get(ArryListOptLine.get(i+1)-1).y )* panelSize.height/9;
Color colCurrent=g.getColor();
g.setColor(Color.green);
g.setStroke(new BasicStroke(3.0f));
g.drawLine((int)OptmapPointX1,(int)OptmapPointY1,(int)OptmapPointX2,(int)OptmapPointY2);
g.setColor(colCurrent);
g.setStroke(new BasicStroke());
}
}
}
{
Graphics2D g=(Graphics2D) ge;
super.paintComponent(g); //显示白色，如果没有super则显示灰色
panelSize = getSize();
RectPoint=this.getLocation();//getLocation()获得当前组件的屏幕坐标
//g.setColor(Color.gray);
g.setColor(Color.green);
//绘制X、Y轴
g.drawLine(10,panelSize.height-10,10,0);
g.drawLine(10,panelSize.height-10,panelSize.width,panelSize.height-10);
g.drawString("0",3,panelSize.height-2);
g.drawString(new Integer((int)(panelSize.height/10)).toString(),20,20);
g.drawString(new Integer((int)(panelSize.width/10)).toString(),panelSize.width-30,panelSize.height-20);
//绘制Y轴箭头
g.drawLine(panelSize.width,panelSize.height-10,panelSize.width-10,panelSize.height-5);
g.drawLine(panelSize.width,panelSize.height-10,panelSize.width-10,panelSize.height-15);
//绘制X轴箭头
g.drawLine(10,0,5,5);
g.drawLine(10,0,15,5);
//绘制刻度
//绘制Y轴刻度
int isomerous1 = panelSize.width/10;
for(int j = 0;j<isomerous1 ;j++)
{
g.drawLine(j*10,panelSize.height-10,j*10,panelSize.height-15);
}
//绘制X轴刻度
int isomerous2 =panelSize.height/10;
for(int j = 0;j<isomerous2 ;j++)
{
g.drawLine(10,panelSize.height-j*10,15,panelSize.height-j*10);
}
//to draw Logistics map Sides
for(Side iterator : mapSide)
{
float mapPointX1=30+(ArryListLine.get(iterator.getNode()-1).x )* panelSize.width/12;
float mapPointY1=30+(ArryListLine.get(iterator.getNode()-1).y )* panelSize.height/9;
float mapPointX2=30+(ArryListLine.get(iterator.getPreNode()-1).x )* panelSize.width/12;
float mapPointY2=30+(ArryListLine.get(iterator.getPreNode()-1).y )* panelSize.height/9;
int X1=(int)mapPointX1; int Y1=(int) mapPointY1;
int X2=(int)mapPointX2; int Y2=(int) mapPointY2;
Color colorCurrent=g.getColor();
g.setColor(Color.orange);
g.setStroke(new BasicStroke(2.0f));
g.drawOval(X1-2,Y1-2, 6, 6);
g.drawString(new Integer(mapSide.get(0).getPreNode()).toString(), (int)(0.4*panelSize.width/12+30-5),(int)(1.0*panelSize.height/9+30-5));
g.drawString(new Integer( iterator.getNode()).toString(),X1-5,Y1-5);
g.drawOval(X2-2,Y2-2, 6, 6);
g.setStroke(new BasicStroke());
g.setColor(Color.gray);
g.drawLine(X1,Y1,X2,Y2);
g.setColor(colorCurrent);
//to draw the minishort path ,the elements of ArryListOptLine are added into ArryListOptLine in Dijkatra class.
for(int i=0;i<ArryListOptLine.size()-1;i++)
{
g.setColor(Color.blue);
g.setStroke(new BasicStroke(0.5f));
float PointX1=0+(ArryListLine.get(ArryListOptLine.get(0)-1).x)* panelSize.width/12;
float PointY1=0+(ArryListLine.get(ArryListOptLine.get(0)-1).y)* panelSize.height/9;
float PointX2=60+(ArryListLine.get(ArryListOptLine.get(ArryListOptLine.size()-1)-1).x )* panelSize.width/12;
float PointY2=150+(ArryListLine.get(ArryListOptLine.get(ArryListOptLine.size()-1)-1).y )* panelSize.height/9;
g.drawRect((int)PointX1,(int)PointY1,((int)PointX2-(int)PointX1),((int)PointY2-(int)PointY1) );
float OptmapPointX1=30+(ArryListLine.get(ArryListOptLine.get(i)-1).x)* panelSize.width/12;
float OptmapPointY1=30+(ArryListLine.get(ArryListOptLine.get(i)-1).y)* panelSize.height/9;
float OptmapPointX2=30+(ArryListLine.get(ArryListOptLine.get(i+1)-1).x )* panelSize.width/12;
float OptmapPointY2=30+(ArryListLine.get(ArryListOptLine.get(i+1)-1).y )* panelSize.height/9;
Color colCurrent=g.getColor();
g.setColor(Color.green);
g.setStroke(new BasicStroke(3.0f));
g.drawLine((int)OptmapPointX1,(int)OptmapPointY1,(int)OptmapPointX2,(int)OptmapPointY2);
g.setColor(colCurrent);
g.setStroke(new BasicStroke());
}
}
}
不足之处
程序使用的是有向图的方法，对于起点编号在右而终点编号在左和点之间不能得到优化的路径。
需要源码请留言。