最短路径-有向无环图

有向无环图最短路径

根据算法基础这本书的思路，先进行拓扑排序，在逐一进行松弛操作。

package com.jeff.demon;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

public class ShortestLineAppTest {
    //有向无环图求最短路径
    @Test
    public void test0(){
        RouteNode a=new RouteNode("a");
        RouteNode b=new RouteNode("b");
        RouteNode c=new RouteNode("c");
        RouteNode d=new RouteNode("d");
        RouteNode e=new RouteNode("e");
        RouteNode a0=new RouteNode("a0");
        a.routeNodeWeightList.add(new RouteNodeWeight(b,1));
        b.routeNodeWeightList.add(new RouteNodeWeight(c,2));
        b.routeNodeWeightList.add(new RouteNodeWeight(d,3));
        c.routeNodeWeightList.add(new RouteNodeWeight(e,4));
        d.routeNodeWeightList.add(new RouteNodeWeight(e,5));
        a0.routeNodeWeightList.add(new RouteNodeWeight(d,6));
        startRouteNode(Arrays.asList(
                a,b,c,d,e,a0
        ));
    }

    void startRouteNode(List<RouteNode> routeNodeList){
        InOutDegree inOutDegree=new InOutDegree(routeNodeList);
        inOutDegree.calcIndegree();
        Map<RouteNode,Integer> shortestPath=routeNodeList.stream().collect(Collectors.toMap(e->e,e->-1));
        routeNodeList.stream().collect(Collectors.toMap(e->e,e->0));
        for (RouteNode routeNode : inOutDegree.topologicSort()) {
               relax(routeNode,shortestPath);
        }
        System.out.println(shortestPath);
    }

    //松弛操作
    void relax(RouteNode routeNode,Map<RouteNode,Integer> shortestPath){
        if(shortestPath.get(routeNode)==-1){
            shortestPath.put(routeNode,0);
        }
        int preShorest=shortestPath.get(routeNode);
        routeNode.routeNodeWeightList.forEach(e->{
            if(shortestPath.get(e.routeNode)==-1){
                shortestPath.put(e.routeNode,preShorest+e.weight);
            }else{
                int next=shortestPath.get(e.routeNode);
                if(preShorest+e.weight<next){
                    shortestPath.put(e.routeNode,preShorest+e.weight);
                }
            }
        });
    }

    static class InOutDegree{
        Map<RouteNode,Integer> indegreeMap=new HashMap<>();//节点入度数
        Map<RouteNode,Integer> outdegreeMap=new HashMap<>();//节点出度数
        List<RouteNode> sourceList;
         InOutDegree(List<RouteNode> routeNodeList)  {
            sourceList=routeNodeList;
        }

        //设置入度
        void calcIndegree(){
            indegreeMap=sourceList.stream().collect(Collectors.toMap(e->e,e->0));
            for (RouteNode routeNode : sourceList) {
                routeNode.routeNodeWeightList.forEach(e->{
                            indegreeMap.computeIfPresent(e.routeNode,(k,oldValue)->oldValue+1);
                        }
                );
            }
        }

        List<RouteNode> topologicSort(){
            List<RouteNode> topologicSortList=new LinkedList<>();
            topologicSort0(topologicSortList);
            return topologicSortList;
        }

        //提取入度为0的，并相应地对相关节点入度-1
       void topologicSort0(List<RouteNode> topologicSortList){
             while(!indegreeMap.isEmpty()){
                 List<RouteNode> routeNodeList=indegreeMap.entrySet().stream().filter(e->e.getValue()==0).map(Map.Entry::getKey)
                         .collect(Collectors.toList());
                 routeNodeList.forEach(e->{
                             indegreeMap.remove(e);
                             for (RouteNodeWeight routeNodeWeight : e.routeNodeWeightList) {
                                 RouteNode routeNode0=routeNodeWeight.routeNode;
                                 indegreeMap.compute(routeNode0,(k,o)->o-1);
                             }
                         }
                 );
                 topologicSortList.addAll(routeNodeList);
             }
        }

        //设置出度
        void addOutdegree(){
            for (RouteNode routeNode : sourceList) {
                outdegreeMap.put(routeNode,routeNode.routeNodeWeightList.size());
            }
        }
    }


    static class RouteNode{
        String nodeName;//本节点名称
        List<RouteNodeWeight> routeNodeWeightList=new LinkedList<>();//可达节点和对应权重
        public RouteNode(String name){
            this.nodeName=name;
        }
        @Override
        public String toString(){
            return this.nodeName;
        }
    }

    static class RouteNodeWeight{
        RouteNode routeNode;
        int weight;
        public RouteNodeWeight(RouteNode routeNode,int weight){
            this.routeNode=routeNode;
            this.weight=weight;
        }
    }
}