allbetgmaing下载:你已经是个成熟的程序员了,该学会用程序帮自己省钱了————狄克斯特拉算法

admin 2周前 (06-28) 科技 6 0

  提及回家,路途漫漫,行李满满,尤其我等村里交通不发达的地方,可能连直达的票都没有,虽说条条大陆通罗马,但究竟照样想找个换乘最少的门路,究竟谁不想回家更轻松点呢(*^_^*),下面就是我回家的所有门路。

 

  思绪很简单,先找起点看是否能到,不能到的话,看起点能到的点的下一步是否能到

 

  话不多说,撸代码:

public static void main(String[] args) {
    HashMap<String,List<String>> data = new HashMap<String, List<String>>();
    List<String> list1 = new ArrayList<String>();
    data.put("起点",list1);
    list1.add("A");
    list1.add("B");
    List<String> list2 = new ArrayList<String>();
    data.put("A",list2);
    list2.add("终点");
    List<String> list3 = new ArrayList<String>();
    data.put("B",list3);
    list3.add("A");
    list3.add("终点");
    query(data,"终点","起点");
}

public static void query(Map<String,List<String>> data, String queryValue, String start){
    if(data==null || queryValue ==null){
        return;
    }
    Queue<String> queue = new LinkedList<String>();
    Map quaryLog  = new HashMap();
    Map<String,List<String>> routes = new HashMap<String, List<String>>();
    queue.offer(start);
    quaryLog.put(start,"");
    String parent = null;
    while (!queue.isEmpty()){
        parent = queue.poll();
        List<String> values = data.get(parent);
        for(String value:values){
            List<String> r = new ArrayList<String>();
            if(routes.containsKey(parent)){
                r.addAll(routes.get(parent));
            }
            r.add(parent);
            routes.put(value,r);
            if(queryValue.equals(value)){
                routes.get(value).add(value);
                System.out.println(routes.get(value));
                return;
            }
            if(!quaryLog.containsKey(value)){
                queue.offer(value);
                quaryLog.put(value,"");
            }
        }
    }
    return ;
}

  

  run 一把,效果出来了

  [起点, A, 终点]

  终于,效果出来了,先到A地,再从A到终点,实在这就是广度优先搜索,so easy兴冲冲去买票,发现钱不够,哎,没有思量票价啊!!!我的票价是这样的:

 

  根据现在的计划需要700元,可是我只有650元,不够啊,没办法,修改算法把,这次需要把价钱思量进去,我需要最廉价的门路

  思绪也类似,先从起点最先走,划分盘算最廉价的门路

 allbetgmaing下载:你已经是个成熟的程序员了,该学会用程序帮自己省钱了————狄克斯特拉算法 第1张

  终点暂时到不了,我们把到终点的距离记作无限,接着我们从B点最先往下找,盘算最廉价的价钱如下:

 allbetgmaing下载:你已经是个成熟的程序员了,该学会用程序帮自己省钱了————狄克斯特拉算法 第2张

  然后再盘算A点走的话,最廉价的门路,比从B点走廉价的话我们就更新,不廉价的话代表原来的价钱已经是最廉价的了

 allbetgmaing下载:你已经是个成熟的程序员了,该学会用程序帮自己省钱了————狄克斯特拉算法 第3张

  找到了,最廉价的门路是600,然则程序要如何做呢,究竟我以后不仅要回家,还要去旅游,还要去丈母外家,我要每次都最廉价!!!,撸码如下:

  
public static void main(String[] args) {
HashMap<String,HashMap<String,Integer>> data = new HashMap<String, HashMap<String, Integer>>();
HashMap<String,Integer> map1 = new HashMap<String, Integer>();
data.put("起点",map1);
map1.put("A",600);
map1.put("B",200);
HashMap<String,Integer> map2 = new HashMap<String, Integer>();
data.put("A",map2);
map2.put("终点",100);
HashMap<String,Integer> map3 = new HashMap<String, Integer>();
data.put("B",map3);
map3.put("终点",500);
map3.put("A",300);
queryMinPrice(data,"起点","终点");
}

public static void queryMinPrice(HashMap<String,HashMap<String,Integer>> data,String start,String end){
HashMap<String,Integer> costs = new HashMap<String, Integer>();
HashMap<String,List<String>> route = new HashMap<String, List<String>>();
for(Map.Entry<String,Integer> entry: data.get(start).entrySet()){
costs.put(entry.getKey(),entry.getValue());
List<String> list = new ArrayList<String>();
list.add(entry.getKey());
route.put(entry.getKey(),list);
}
costs.put(end,Integer.MAX_VALUE);
HashMap<String,String> queryLog = new HashMap<String, String>();
String key = findMinPriceKey(costs,queryLog);
while (key != null){
queryLog.put(key,"");
if(data.get(key) == null){
break;
}
for(Map.Entry<String,Integer> entry:data.get(key).entrySet()){
if(costs.containsKey(entry.getKey())){
if(entry.getValue()+costs.get(key)<costs.get(entry.getKey())){
costs.put(entry.getKey(),entry.getValue()+costs.get(key));
List<String> list = new ArrayList<String>();
list.addAll(route.get(key));
list.add(entry.getKey());
route.put(entry.getKey(),list);
}
}else {
costs.put(entry.getKey(),entry.getValue()+costs.get(key));
List<String> list = new ArrayList<String>();
list.addAll(route.get(key));
route.put(entry.getKey(),list);
}
}
key = findMinPriceKey(costs,queryLog);
}
System.out.println("最小破费:"+costs.get(end));
System.out.println("最小破费路径:"+route.get(end));
}
private static String findMinPriceKey(HashMap<String,Integer> data,HashMap<String,String> queryLog){
String key = null;
for(Map.Entry<String,Integer> entry : data.entrySet()){
if(!queryLog.containsKey(entry.getKey()) && key == null ){
key = entry.getKey();
}
if(!queryLog.containsKey(entry.getKey()) && entry.getValue()<data.get(key)){
key = entry.getKey();
}
}
return key;
}

  运行效果:

  最小破费:600

  最小破费路径:[B, A, 终点]

  效果出来了,先买到B的票,然后在到A,再回家,只要600块,还能省50块,完善!!这就是赫赫有名的狄克斯特拉算法。

,

欧博亚洲APP下载

欢迎进入欧博亚洲APP下载(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

网友评论

  • (*)

最新评论

文章归档

站点信息

  • 文章总数:517
  • 页面总数:0
  • 分类总数:8
  • 标签总数:849
  • 评论总数:161
  • 浏览总数:3309