Dijkstra shortest path algorithm to optimize combat

sponsored links
Recently done in order to achieve a functional system, find the map of the shortest path between two points, using Java. Naturally think of the Dijkstra algorithm to the time complexity of O (n ^ 2), our system is also necessary to the path through all the points are saved, it will introduce additional complexity.
Dijkstra algorithm is described in the Portal: http://baike.baidu.com/view/7839.htm?fr=ala0_1_1
First step, not to discuss the complexity, the first step first step to achieve the most basic functions, so with the first version of the code.
/**
 *  Point  
 * @author Jason Wen
 *
 */
public class Point {
        private String name;
        // Longitude  
        private double x = 0;
        // Latitude  
        private double y = 0;
        private int lu = 0;
        // Is a junction  
        private boolean isCross;
        // Is a red point, if the source point to the point of the shortest paths have been determined from  , This point becomes red dot  
        private boolean isRed;
        // Is a source of  
        private boolean isSource;
  
        constructor & setter/getter
}

/**
 *  Edge, any connected two points constitute an edge  
 *  Properties include start, end point  , Length  
 * @author Jason Wen
 *
 */
public class Edge {
        private Point start;
        private Point end;
        private double length;

        constructor & setter/getter
}

/**
 *  The shortest path, property includes the source point  , The end, the path to the collection of all the points  , Length  
 * @author Jason Wen
 *
 */
public class Path {
        private Point source;
        private Point end;
        private List<Point> points;
        private double length;

        constructor & setter/getter
}

public class Dijkstra {
        private List<Point> points;
        private List<Edge> edges = new ArrayList<Edge>();;
        private List<Path> paths = new ArrayList<Path>();
        // The current changes to a red point  
        private Point currentPoint;
        private final double INFINITY = 999999;
        // The source points to the current length of the red point  
        private double startToCurrent;
        
        /**
         *  Initialize the source point to other points of paths, i.e.  Path
         */
        public void init(){
                Point source = null;
                for (Point point : points) {
                        if (point.isSource()) {
                                source = point;
                        }
                }
                // Set the path's end  
                for (Point point : points) {
                        List<Point> redPoints = new ArrayList<Point>();
                        redPoints.add(source);
                        Path path = new Path(source,point,redPoints,INFINITY);
                        paths.add(path);
                }
                // Set the length of the path, if there is such a boundary  : Starting, ending point respectively and the source of the path points  , End the same  
                for (Path path : paths) {
                        for (Edge edge: edges) {
                                if (path.getSource().getName().equals(edge.getStart().getName())&&path.getEnd().getName().equals(edge.getEnd().getName())) {
                                        path.setLength(edge.getLength());
                                }
                        }
                }
        }
        
        public void dijkstra(){
                dijkstra(null);
        }
        
        public void dijkstra(Point end){
                init();
                for (int i = 0; i < paths.size(); i++) {
                        int indexMin = getMin();
                        double minDist = paths.get(indexMin).getLength();
                        if (minDist==INFINITY) {
                                System.out.println(" There are unreachable vertex  ");
                        }else if(i!=paths.size()-1){
                                // Gets the current cycle already find the shortest path point  
                    currentPoint = paths.get(indexMin).getEnd();
                    paths.get(indexMin).getPoints().add(currentPoint);
                    startToCurrent = minDist;
                }
                        // Sets the current point is set to red dot  
                        for (Point point : points) {
                                if (point.getName().equals(currentPoint.getName())) {
                                        point.setRed(true);
                                        if (end!=null&&end.getName().equals(point.getName())) {
                                                return;
                                        }
                                }
                        }
                        resetPaths();
                }
        }

        /**
         *  Gets the collection of the path length of the smallest index value  
         * @return
         */
        private int getMin() {
                double minDist = INFINITY;
        int indexMin = 0;
                for (int i = 0; i < paths.size(); i++) {
                        Path path = paths.get(i);
                        if (!path.getEnd().isRed()&&path.getLength()<minDist) {
                                minDist = path.getLength();
                                indexMin = i;
                        }
                }
                return indexMin;
        }

        /**
         *  In the current red dot changes, sources point to another point of the path with the appropriate changes  , Through the current red dot  ,
         *  Not to the point before you may become reachable  ,
         *  Before you reach the point of the path length changes  
         *  So you want to reset other path length  
         */
        private void resetPaths() {
                for (Path path : paths) {
                        if (path.getEnd().isRed()) {
                                continue;
                        }
                        for (Edge edge: edges) {
                                if (edge.getStart().getName().equals(currentPoint.getName())&&edge.getEnd().getName().equals(path.getEnd().getName())) {
                                        double currentToFringe = side.getLength();
                                        double startToFringe = startToCurrent + currentToFringe;
                                        double pathLength = path.getLength();
                                        if(startToFringe<pathLength) {
                          path.getPoints().add(currentPoint);
                          path.setLength(startToFringe);
                                        }
                                }
                        }
                }
                
        }
        
        public void display(){
                for (Path path : paths) {
                        System.out.print(path.getSource().getName()+"-->"+path.getEnd().getName()+":");
                        for (Point point : path.getPoints()) {
                                System.out.print(point.getName()+"  ");
                        }
                        System.out.print(path.getLength());
                        System.out.println();
                }
        }


        setter/getter
}       


Test
public class Client {
        public static void main(String[] args) {
                long initBegin = System.currentTimeMillis();
                Point A = new Point("A");
                Point B = new Point("B");
                Point C = new Point("C");
                Point D = new Point("D");
                Point E = new Point("E");
                Point F = new Point("F");
                Point G = new Point("G");
                Point H = new Point("H");
                Point I = new Point("I");
                Point J = new Point("J");
                Point K = new Point("K");
                Point L = new Point("L");
                A.setRed(true);
                A.setSource(true);
                
                List<Point> points = new ArrayList<Point>();
                points.add(B);
                points.add(A);
                points.add(C);
                points.add(D);
                points.add(E);
                points.add(F);
                points.add(G);
                points.add(H);
                points.add(I);
                points.add(J);
                points.add(K);

//              for (int i = 0; i < 10000; i++) {
//                      Point point = new Point(""+i);
//                      points.add(point);
//              }
                
                List<Edge> edges = new ArrayList<Edge>();
                edges.add(new Edge(A,B,19));
                edges.add(new Edge(B,C,25));
                edges.add(new Edge(B,D,8));
                edges.add(new Edge(C,E,10));
                edges.add(new Edge(D,A,20));
                edges.add(new Edge(D,C,4));
                edges.add(new Edge(D,E,12));
                
                edges.add(new Edge(A,E,13));
                edges.add(new Edge(B,F,25));
                edges.add(new Edge(C,F,2));
                edges.add(new Edge(D,F,10));
                
                edges.add(new Edge(F,I,20));
                edges.add(new Edge(F,K,16));
                edges.add(new Edge(C,G,5));
                edges.add(new Edge(G,I,10));
                edges.add(new Edge(G,K,1));
                edges.add(new Edge(G,H,7));
                edges.add(new Edge(H,J,20));
                edges.add(new Edge(H,K,45));
                edges.add(new Edge(I,J,4));
                edges.add(new Edge(J,K,3));

//              for (int i = 0; i < points.size(); i++) {
//                      for (int j = i; j < points.size()-i+1; j++) {
//                              if (j<points.size()&&(j==i+1||j==10*i+1)) {
//                                      edges.add(new Edge(points.get(i),points.get(j),100*Math.random()));
//                              }
//                      }
//              }

                System.out.println(edges.size());
                long initEnd = System.currentTimeMillis();
                System.out.println("init time:"+(initEnd-initBegin)/60);
                
                long computeBegin = System.currentTimeMillis();
                Dijkstra dijkstra = new Dijkstra();
                dijkstra.setPoints(points);
                dijkstra.setEdges(edges);
                dijkstra.dijkstra(A);
                dijkstra.display();
                long computeEnd = System.currentTimeMillis();
                System.out.println("compute time:"+(computeEnd-computeBegin)/1000);
        }
}

Blessings, the results came out, Long March to sell the first step. Let's look at how that performance, open the comments section, simulation 1w points, 6k edges, run. (N minutes later) Hey, that Eclipse is not a small red light on how to burn out, this this this, Sha did not say, change it.
Look at the code written before the Bulkhead, dijkstra (Point end); and resetPaths (); a total of 3 layers nested for loop, this complexity can be is O (n ^ 3), than the most basic Dijkstra algorithm complexity is higher , change it.
Analysis of a moment, decided to resetPaths () this method to start, because the initial design of this method have a problem, reset all the paths do not need every time and all the side for comparison, I need is popular spots Bianhua When all the red points from the side of the path of the end of the match can make changes, so use the List Storage Path becomes feasible, while the Map is a good storage structure, value for the Path, key to the end of this Path.
This code has been optimized for the first time
public class DijkstraO {
        private List<Point> points;
        private List<Edge> edges = new ArrayList<Edge>();
        //Point is the end of the Path
        private Map<Point, Path> pathMap = new HashMap<Point, Path>();
        // The current changes to a red point  
        private Point currentPoint;
        private final double INFINITY = 999999;
        // The source points to the current length of the red point  
        private double startToCurrent;
        
        /**
         *  Initialize the source point to other points of paths, i.e.  Path
         */
        public void init(Point start){
                start.setSource(true);
                start.setRed(true);
                Point source = start;
                // Set the path's end  
                for (Point point : points) {
                        List<Point> redPoints = new ArrayList<Point>();
                        redPoints.add(source);
                        Path path = new Path(source,point,redPoints,INFINITY);
                        pathMap.put(point, path);
                }
                // Set the length of the path, if there is such a boundary  : Starting, ending point respectively and the source of the path points  , End the same  
                for (Edge edge : edges) {
                        if (source.getName().equals(edge.getStart().getName())) {
                                pathMap.get(edge.getEnd()).setLength(edge.getLength());
                        }
                }
        }
        
        public void dijkstra(){
                dijkstra(null,null);
        }
        
        public void dijkstra(Point start,Point end){
                long startInit = System.currentTimeMillis();
                init(start);
                System.out.println("dijkstra init time:"+(System.currentTimeMillis()-startInit));
                for (int i = 0; i < points.size(); i++) {
                        int indexMin = getMin();
                        double minDist = pathMap.get(points.get(indexMin)).getLength();
                        if (minDist==INFINITY) {
                                System.out.println(" There are unreachable vertex  ");
                        }else if(i!=points.size()-1){
                                // Gets the current cycle already find the shortest path point  
                                currentPoint = points.get(indexMin);
                    points.get(indexMin).setRed(true);
                    if (end!=null&&end.equals(currentPoint)) {
                                        return;
                                }
                    pathMap.get(points.get(indexMin)).getPoints().add(currentPoint);
                    startToCurrent = minDist;
                }
                        
                        resetPaths();
                }
        }
        
        private int getMin() {
                double minDist = INFINITY;
        int indexMin = 0;
                for (int i = 0; i < points.size(); i++) {
                        Path path = pathMap.get(points.get(i));
                        if (!path.getEnd().isRed()&&path.getLength()<minDist) {
                                minDist = path.getLength();
                                indexMin = i;
                        }
                }
                return indexMin;
        }

        /**
         *  In the current red dot changes, sources point to another point of the path with the appropriate changes  , Through the current red dot  ,
         *  Not to the point before you may become reachable  ,
         *  Before you reach the point of the path length changes  
         *  So you want to reset other path length  
         */
        private void resetPaths() {
                for (Edge edge : edges) {
                        if (edge.getEnd().isRed()) {
                                continue;
                        }
                        Path path = pathMap.get(edge.getEnd());
                        if (edge.getStart().getName().equals(currentPoint.getName())&&edge.getEnd().getName().equals(path.getEnd().getName())) {
                                double currentToFringe = edge.getLength();
                                double startToFringe = startToCurrent + currentToFringe;
                                double pathLength = path.getLength();
                                if(startToFringe<pathLength) {
                                        List<Point> points = pathMap.get(currentPoint).getPoints();
                                        List<Point> copyPoints = new ArrayList<Point>();
                                        for (Point point : points) {
                                                copyPoints.add(point);
                                        }
                                        path.setPoints(copyPoints);
                  path.setLength(startToFringe);
                                }
                        }
                }
        }
        
        public void display(){
                for (Point point : pathMap.keySet()) {
                        Path path = pathMap.get(point);
                        System.out.print(path.getSource().getName()+"-->"+path.getEnd().getName()+":");
                        for (Point point2 : path.getPoints()) {
                                System.out.print(point2.getName()+"  ");
                        }
                        System.out.print(path.getLength());
                        System.out.println();
                }
        }


        setter/getter
}

The new program, path to the storage structure from the List Map <Point, Path> pathMap, so that resetPaths () this method only on the edge of the circle all you can, each loop, through the edge of the end point Find a key path, and then reset the length of their conduct. This method has a nested for, this is the path through the point set by a deep copy, very little data on the impact of complexity is negligible. In this way, reduce the complexity of the algorithm is O (n ^ 2). Test, 15 seconds the result. Although this result is not satisfactory, but he was not a people wistfully.
It ran real data about it, 3w points, 8w edges. start -> not end -> not end -> not end -> ... 15 minutes later -> end, I am very sad that this thing can do to BOSS? The answer of course is no.
Keep going, google to the paper "Fast Dijkstra Shortest Path Algorithm" , repeatedly looked at times, than for my code, and then analyzed. How to reduce the complexity of the functions of the current terms, reduce the nesting cycle is very difficult, since it can not reduce the number of cycles, it is to reduce the dijkstra () method in the points.size (), and resetPaths () The edges.size (). Analyze again, why should we carry out these two collections cycle, our objective? The key is to change the red dot, and then look back resetPaths () of the Notes "in the current red dot changes, the source point to other points of the path changes accordingly", which means that after the change in the red dot, and Red Dot related point, also is a red dot for the starting point of the edge of the end point of change, this change is it? Look again notes, "before not to the point may become accessible, accessible point prior to the path length will change." The outlook is relatively clear, and we need to cycle the point of these changes, the other point we do not need hell.
Optimized in accordance with this idea, we will point these changes as blue points, stored in the Set <Point> bluePoints in. Blue point set, kept two points, 1. Initialization phase Path.length! = INFINITY, 2.resetPath method reset-off point. Then construct two Map <Point, List <Edge>>, respectively, the starting point and end point for the key. Map to the starting point for the key role of the red point changes, find the starting point to the red dot to the end point of all sides, and insert the blue point set. To end point for the key role of Map in resetPaths, find the end all to this point as the point of all edges, and then follow-up of reset operation.
Optimized code:
public class DijkstraO3 {
        private List<Point> points;
        private List<Edge> edges = new ArrayList<Edge>();
        //Point is the end of the Path
        private Map<Point, Path> pathMap = new HashMap<Point, Path>();
        //Point is the start of all Edge in the List
        private Map<Point, List<Edge>> edgesMapByStart = new HashMap<Point, List<Edge>>();
        //Point is the end of all Edge in the List
        private Map<Point, List<Edge>> edgesMapByEnd = new HashMap<Point, List<Edge>>();
        // Blue point set, where two points  ,1. The initialization phase  Path.length!=INFINITY
        //2.resetPath  Method to reset the point  
        private Set<Point> bluePoints = new HashSet<Point>();
        private Point currentPoint;
        private final double INFINITY = 999999;
        private double startToCurrent;
        
        public void init(Point start){
                start.setSource(true);
                start.setRed(true);
                Point source = start;
                for (Point point : points) {
                        List<Point> redPoints = new ArrayList<Point>();
                        redPoints.add(source);
                        Path path = new Path(source,point,redPoints,INFINITY);
                        pathMap.put(point, path);
                }
                for (Edge edge : edges) {
                        Point s = edge.getStart();
                        Point e = edge.getEnd();
                        if (source.equals(s)) {
                                pathMap.get(e).setLength(edge.getLength());
                                bluePoints.add(e);
                        }
                        if (edgesMapByStart.get(s)==null) {
                                edgesMapByStart.put(s, new ArrayList<Edge>());
                                edgesMapByStart.get(s).add(edge);
                        }else{
                                edgesMapByStart.get(s).add(edge);
                        }
                        if (edgesMapByEnd.get(e)==null) {
                                edgesMapByEnd.put(e, new ArrayList<Edge>());
                                edgesMapByEnd.get(e).add(edge);
                        }else{
                                edgesMapByEnd.get(e).add(edge);
                        }
                }
        }
        
        public void dijkstra(){
                dijkstra(null,null);
        }
        
        public void dijkstra(Point start,Point end){
                long startInit = System.currentTimeMillis();
                init(start);
                System.out.println("dijkstra init time:"+(System.currentTimeMillis()-startInit));
                while (bluePoints.size()>0) {
                        Point point = getMin();
                        if (point==null) {
                                continue;
                        }
                        double minDist = pathMap.get(point).getLength();
                        if (minDist==INFINITY) {
                                System.out.println(" There are unreachable vertex  ");
                        }else {
                    currentPoint = point;
                    point.setRed(true);
                    List<Edge> edges = edgesMapByStart.get(point);
                    if (edges!=null) {
                        for (Edge edge : edges) {
                                if (!edge.getEnd().isRed()) {
                                        bluePoints.add(edge.getEnd());
                                }
                        }
                                        
                                }
                    bluePoints.remove(point);
                    if (end!=null&&end.equals(currentPoint)) {
                                        return;
                                }
                    pathMap.get(point).getPoints().add(currentPoint);
                    startToCurrent = minDist;
                }
                        
                        resetPaths();
                }
        }

        private void resetPaths() {
                Iterator<Point> it = bluePoints.iterator();
                while (it.hasNext()) {
                        Point bluePoint = it.next();
                        List<Edge> edges = edgesMapByEnd.get(bluePoint);
                        for (Edge edge : edges) {
                                if (edge.getEnd().isRed()) {
                                        continue;
                                }
                                Path path = pathMap.get(edge.getEnd());
                                if (edge.getStart().equals(currentPoint)&&edge.getEnd().equals(path.getEnd())) {
                                        double currentToFringe = edge.getLength();
                                        double startToFringe = startToCurrent + currentToFringe;
                                        double pathLength = path.getLength();
                                        if(startToFringe<pathLength) {
                                                List<Point> points = pathMap.get(currentPoint).getPoints();
                                                List<Point> copyPoints = new ArrayList<Point>();
                                                for (Point point : points) {
                                                        copyPoints.add(point);
                                                }
                                                path.setPoints(copyPoints);
                                                path.setLength(startToFringe);
                                        }
                                }
                        }
                }
        }
        
        public void display(){
                for (Point point : pathMap.keySet()) {
                        Path path = pathMap.get(point);
                        System.out.print(path.getSource().getX()+"-->"+path.getEnd().getX()+":");
                        for (Point point2 : path.getPoints()) {
                                System.out.print(point2.getX()+"  ");
                        }
                        System.out.print(path.getLength());
                        System.out.println();
                }
        }
        
        private Point getMin() {
                double minDist = INFINITY;
        Point point = null;
                for (Point bluePoint : bluePoints) {
                        Path path = pathMap.get(bluePoint);
                        if (!path.getEnd().isRed()&&path.getLength()<minDist) {
                                minDist = path.getLength();
                                point = bluePoint;
                        }
                        
                }
                return point;
        }


        setter/getter
}

Test, Bingo, Pirates of Jingle Bells by lightning Jen did not allow business world is full of love you Jane Jane trend I love you, second buttoned.
Records about the results of optimization, in 1w points, 6k edges of the test data, the computing time from the N min -> 15 seconds. Optimization results in 15 seconds fought 3w real data points, 8w edges, the computation time soared to 15 minutes, the final optimization to 1 second. This performance enhancement should be said that very high up.
Go back to the realization of this algorithm, first of all, regardless of the performance of the first to achieve functionality. This subsequent optimization of the accuracy of test security. Then, to replace part of the Map List, direct access with the key value, directly reduce the level nested. Finally, the analysis of the feasibility of optimization, this method can be ruled out, and then analyze the optimization feasible, seize key points of the problem, eliminate unnecessary operations.
  • del.icio.us
  • StumbleUpon
  • Digg
  • TwitThis
  • Mixx
  • Technorati
  • Facebook
  • NewsVine
  • Reddit
  • Google
  • LinkedIn
  • YahooMyWeb

Related Posts of Dijkstra shortest path algorithm to optimize combat

  • Hibernate II Study Notes

    11. Many-to-many Of many that can be converted to two one-to-many <set name="students" table="teacher_student"> <key column="techer_id"/> <many-to-many column="student_id"/> </set> many-to-many data only from one end of the mainten

  • hibernate (jpa) composite primary key annotation statement Ways

    In the design of the database tables are designed with a composite primary key of the table, that table's record by more than one field joint identification, such as: Table CREATE TABLE TB_HOUR_DATA ( STAT_DATE DATE NOT NULL, PATH_ID NUMBER(20) NOT NULL,

  • EJB

    public transient int counter; / / transient property private String firstname; / / persistent property @ Transient String getLengthInMeter () (...) / / transient property String getName () (...) / / persistent property @ Basic int getLength () (...) / / p

  • jboss ejb3 Message Driven Bean

    Super Medium ejb hate. . . . . . . . . . . . . . . . . . . ================================================ To configure a Message Driven Bean in a different application server parameters are not the same. Currently only passed the test jboss. Message Dri

  • hibernate call stored procedure

    hibernate call stored procedure

  • Based on Spring's Hibernate Search full-text search function of sample

    Database: Oracle 9i JDBC Driver: OJDBC14 Development Environment: Eclipse-JEE Spring version: Spring 2.0.6 Hibernate version: Hibernate Core 3.2.5/Hibernate Annotation 3.3.0/Hibernate Validator 3.0.0/Hibernate Search 3.0.0 Beta4 / / jdbc.properties (JDBC

  • hibernate using c3p0 connection pooling

    Private http://www.lifevv.com/tenyo/doc/20070605102040991.html c3p0 for open source's JDBC connection pool, with the release hibernate. This article describes how to use the hibernate configuration in c3p0. c3p0 connection pool configuration is v ...

  • hibernate generic generic DAO

    package org.lzpeng.dao; import java.io.Serializable; import java.util.List; import org.hibernate.Criteria; import org.hibernate.Query; import org.hibernate.criterion.Criterion; import org.springside.modules.orm.hibernate.Page; /** * * @version 2009-1-10 *

  • The level Hibernate cache

    Hibernate cache level: (1) a cache is very short and the session life cycle consistent, also known as session-level cache-level cache or transaction-level cache (2) Ways of Supporting level cache: get (); load (); iterator (); only entity object cach ...

  • Great collection of java interview topics

    1, object-oriented features of what has 1. Abstract: Abstract is that it has overlooked a subject has nothing to do with the current goal of those aspects in order to more fully with the current objectives of the attention-related aspects. Abstract does n

blog comments powered by Disqus
Recent
Recent Entries
Tag Cloud
Random Entries