最近看文章看到Dijkstra 算法,想起大学的时候学习的算法导论这门课程
突然就想用java来实现下这个算法了,
以下就来介绍一下这个算法吧.
Dijkstra 算法主要是用来解决有向图单个点到其他点的最短路径的问题
然后我根据这个有向图来编写了Dijkstra 算法
public static void main(String[] args) {
//定义一个有向图
//定义一个集合,所有点的集合
List<String> DOT=new ArrayList<>();
DOT.add("A");
DOT.add("B");
DOT.add("C");
DOT.add("D");
DOT.add("E");
DOT.add("F");
DOT.add("G");
//定义一个集合,所有边到边的距离
Map<String,Integer> EGED=new HashMap<>();
EGED.put("AB",8);
EGED.put("AE",4);
EGED.put("AF",2);
EGED.put("BA",8);
EGED.put("BE",7);
EGED.put("BC",6);
EGED.put("CB",6);
EGED.put("CD",6);
EGED.put("DC",6);
EGED.put("DE",9);
EGED.put("DG",7);
EGED.put("EA",4);
EGED.put("EB",7);
EGED.put("ED",9);
EGED.put("EG",11);
EGED.put("EF",3);
EGED.put("FA",2);
EGED.put("FE",3);
EGED.put("FG",5);
EGED.put("GE",11);
EGED.put("GF",5);
EGED.put("GD",7);
//创建一个被选中的点的集合
LinkedList<String> choose=new LinkedList<>();
String Next=loop("A",DOT,choose,EGED);
String Next1=loop(Next,DOT,choose,EGED);
String Next2=loop(Next1,DOT,choose,EGED);
String Next3=loop(Next2,DOT,choose,EGED);
String Next4=loop(Next3,DOT,choose,EGED);
String Next5=loop(Next4,DOT,choose,EGED);
System.out.println("A"+"---"+Next+"---"+Next1+"---"+Next2+"---"+Next3+"---"+Next4+"---"+Next5);
}
public static String loop(String startPot,List DOT,List choose,Map<String,Integer> EGED){
//把起始点放入,这里我们选择A
choose.add(startPot);
DOT.remove(startPot);
//在边的集合中找到A开始的边
System.out.println(EGED.entrySet());
Map<String,Integer> map=new HashMap<>();
for (String s:EGED.keySet()) {
String TheKey=findroad(s,startPot+"\\w");
if (!("").equals(TheKey))
{
if (map.isEmpty())
{
map.put(TheKey,EGED.get(TheKey));
}else{
if (map.values().iterator().next()>EGED.get(TheKey)){
map.clear();
map.put(TheKey,EGED.get(TheKey));
}
}
}
}
String Next="";
System.out.println(map.entrySet());
for (String s:map.keySet()) {
Next=s.substring(1);
}
System.out.println(Next);
//找到最短路径之后就把所有和这个点相关的路径删除
List a=new ArrayList<>();
for (String sD:EGED.keySet()) {
String TheKey=findroad(sD,"\\w*"+startPot+"\\w*");
if (!("").equals(TheKey))
{
a.add(TheKey);
}
}
for (int i = 0; i < a.size(); i++) {
EGED.remove(a.get(i));
}
System.out.println(EGED.entrySet());
return Next;
}
public static String findroad(String bian,String regEx){
Pattern pattern=Pattern.compile(regEx);
Matcher matcher=pattern.matcher(bian);
if (matcher.find())
{
return bian;
}else{
return "";
}
}以上是代码
以下是运行输出
[GD=7, FA=2, GE=11, GF=5, EA=4, FE=3, EB=7, ED=9, DC=6, CB=6, BA=8, AB=8, BC=6, AE=4, AF=2, BE=7, CD=6, DE=9, EG=11, EF=3, DG=7, FG=5]
[AF=2]
F
[GD=7, GE=11, GF=5, FE=3, EB=7, ED=9, DC=6, CB=6, BC=6, BE=7, CD=6, DE=9, EG=11, EF=3, DG=7, FG=5]
[GD=7, GE=11, GF=5, FE=3, EB=7, ED=9, DC=6, CB=6, BC=6, BE=7, CD=6, DE=9, EG=11, EF=3, DG=7, FG=5]
[FE=3]
E
[GD=7, GE=11, EB=7, ED=9, DC=6, CB=6, BC=6, BE=7, CD=6, DE=9, EG=11, DG=7]
[GD=7, GE=11, EB=7, ED=9, DC=6, CB=6, BC=6, BE=7, CD=6, DE=9, EG=11, DG=7]
[EB=7]
B
[GD=7, DC=6, CB=6, BC=6, CD=6, DG=7]
[GD=7, DC=6, CB=6, BC=6, CD=6, DG=7]
[BC=6]
C
[GD=7, DC=6, CD=6, DG=7]
[GD=7, DC=6, CD=6, DG=7]
[CD=6]
D
[GD=7, DG=7]
[GD=7, DG=7]
[DG=7]
G
[]
A---F---E---B---C---D---G这是初版吧…没时间了..有时间在update一下,
其实dijkstra 算法的核心就是,在一堆有向图中,找一个起始点,然后查看和该点的连接中,最小的那个点,当作下一个起始点, 在本例中,A是出发点,第一次调用该循环的时候,AF-2是最小的,数值是2,所以F点是第二遍的起始点,但是我们已经用过了A,所以在下次循环里面的与A点相关的点我们都给删除掉,在进行循环,当边的那个集合为空时就给退出循环,路径也就找出来了.
当然,本文是最基础的实现,很多东西没考虑好,比如,很多个点怎么办,大量数据的时候怎么办,这么多循环的效率肯定非常低,
欢迎大家给建议,来提升该算法的性能,哈哈哈哈.
以上
2017-2-23