Dijkstra shortest path algorithm to optimize combat

分类:Tech 2010-04-05 来源:CodeWeblog.com 人气:400

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.

分享到:
blog comments powered by Disqus

相关文章

  • Dijkstra shortest path algorithm to achieve a high efficiency 2010-07-03

    Dijkstra shortest path algorithm to achieve a high efficiency [Date :2005-02-07] Source: Journal of Wuhan University of Surveying and Mapping: Lok Yang The bi [font: large, medium] Abstract The existing test summary of some shortest path algorithm ba

  • Dijkstra algorithm C language 2010-10-04

    #ifndef GUIDE_H_INCLUDED #define GUIDE_H_INCLUDED #define MX 1000 // Infinite maximum #define NUM 6 // The maximum number of vertices typedef int adjmatrix[NUM][NUM]; typedef int path[NUM][NUM]; typedef int Dist[NUM];//v0 The distance to the vi int p

  • The single source shortest path - Bellman-Ford algorithm optimization 2011-01-08

    Bellman-Ford single source shortest path to solve the problem, compared to Dijkastra, it is less restrictive: Edge weights can be negative. At the same time, can also detect a negative ring (positive loop). However, the Bellman-Ford ordinary time com

  • Single-source shortest path of SPFA - Shortest Path Faster Algorithm 2011-01-09

    Is very good SPFA the shortest path algorithm, we should grasp. SPFA on the Bellman-Ford algorithm to optimize the key is to realize that: Only those who changed the relaxation of the former over the distance of the point estimates, it may cause the

  • Graph two of the shortest path algorithm to optimize combat 2010-04-05

    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 a ...

  • Single-source shortest path and shortest path for each pair of nodes - Dijkstra and Freud 2011-01-07

    In a diagram, if a node from another node to the existence of the path, the path defined by the length of a path through the weight of the edge and. From one node to a node that there may be multiple paths, the shortest path to which the known shorte

  • Weighted directed graph - the right side of the value of non-negative case of the single-source shortest path problem 2010-06-07

    1. Problem Description: Given a weighted directed graph D with source v, seeking from the other vertex v to D, the shortest path. Limited to one side of the weight is greater than or equal to 0. 2. Java implementation: package boke.graph.shortpath1;

  • Single-source shortest path ---- Dijkstra 2011-05-12

    dijkstra algorithm personal feeling pretty weird, but the complexity of O (n2), fast, but not many people understand the WSM recommended FLOYD, it may be simple, but FLOYD adjacency matrix must be achieved. Function between the two slightly different

  • Single-source shortest path ---- FLOYD 2011-05-12

    FLOYD find the figure for any point on the shortest path, DP, time complexity O (N3), the state transition equation dist [i] [j] = min {dist [i] [j], dist [i] [k] + dist [k] [j]}, dist [i] [j] node i to node j that the shortest path, if dist [i] [j]

iOS 开发

Android 开发

Python 开发

JAVA 开发

开发语言

PHP 开发

Ruby 开发

搜索

前端开发

数据库

开发工具

开放平台

Javascript 开发

.NET 开发

云计算

服务器

Copyright (C) codeweblog.com, All Rights Reserved.

CodeWeblog.com 版权所有 黔ICP备15002463号-1

processed in 0.479 (s). 14 q(s)