Оптимизация графовых алгоритмов для Флойда Warshall алгоритм Джонсона


Я пытаюсь реализовать и сравнивать Флойд и Warshall алгоритм Джонсона(для разреженных графов). Я написал следующий код, который производит правильные выходные значения для всех пар кратчайших путей. Однако теоретически, алгоритм Джонсона должны работать лучше, чем Флойд Warshall на разреженных графах. Однако время работы свидетельствуют об обратном. Я использовал некоторые случайные графы для тестовых целей. Генерация случайных чисел вершин сказать n и пограничным числом между 0 и `Н.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Random;


public class ShortestPaths {

    public static void printArray(double arr[][], int m, int n) {
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                System.out.print(arr[x][y] + "\t\t");
            }
            System.out.println();
        }
    }

    public static int generateRandomBetween(int low, int high) {
        Random r = new Random();
        int result = r.nextInt(high - low) + low;
        return result;
    }

    public static double mean(double[] p) {
        double sum = 0;  // sum of all the elements
        for (int i=0; i<p.length; i++) {
            sum += p[i];
        }
        return sum / p.length;
    }

    public static ArrayList<LinkedList<Integer>> adjacencyList(double g[][], int n){
        //function that takes in input an adjacency matrix and produces and adjacency list
        ArrayList<LinkedList<Integer>> adj_list = new ArrayList<LinkedList<Integer>>();

        //add the vertices
        for(int i=0; i<n; i++){
            adj_list.add(new LinkedList<Integer>());
        }

        //now add the edges
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i!=j || g[i][j] != Double.POSITIVE_INFINITY){
                    adj_list.get(i).add(j);
                }
            }
        }

        return adj_list;
    }

    public void generateGraphs() {
        // n is the number of vertices
        // m is the number of edges

        // m is $m=O(n)$

        int n = 0;
        int m = 0;

        Random r = new Random();

        long startTime = 0;
        long endTime = 0;

        double timeFloyd[] = new double[100];
        double timeJohnson[] = new double[100];

        //ArrayList<LinkedList<Integer>> adj_list;

        for (int i = 0; i < 10; i++) {
            // System.out.println(n + "\t" + m);

            n = ShortestPaths.generateRandomBetween(2, 50); // (1 2) generates 1
                                                            // --- generates
                                                            // inclusive lower
                                                            // value, and higher
                                                            // value - 1
            m = ShortestPaths.generateRandomBetween(0, n);

            // for each n-m pair generate 100 graphs

            for (int k = 0; k < 10; k++) {
                double g[][] = new double[n][n];

                for (int x = 0; x < n; x++) {
                    for (int y = 0; y < n; y++) {
                        if (x != y)
                            g[x][y] = Double.POSITIVE_INFINITY;
                    }
                }

                int count = 0; //counter for number of edges

                while(count != m) {
                    // generate a random edge with a random weight
                    // generate m such edges
                    int from = ShortestPaths.generateRandomBetween(0, n);
                    int to = ShortestPaths.generateRandomBetween(0, n);
                    double weight = r.nextDouble();
                    if (from != to){
                        g[from][to] = weight;
                        count++;
                    }
                }

                // generate adjacency list
                //adj_list = ShortestPaths.adjacencyList(g, n);

                // System.out.println();
                System.out.println("Graph Number : " + i + "\t " + n + "\t " + m);
                startTime = System.nanoTime();
                floydWarshall(g, n, m);
                endTime = System.nanoTime();

                timeFloyd[k] = endTime - startTime;

                startTime = System.nanoTime();
                johnson(ShortestPaths.adjacencyListWeight(g, n), n, m);
                endTime = System.nanoTime();

                timeJohnson[k] = endTime - startTime;

            }

            System.out.println("Time for Floyd Warshall : " + ShortestPaths.mean(timeFloyd));
            System.out.println("Time for Johnson : " + ShortestPaths.mean(timeJohnson));
        }
    }

    static class Vertex implements Comparable<Vertex> {
        private int vertexid;
        private double distance;

        public Vertex(int vertexid, Double distance) {
            this.vertexid = vertexid;
            this.distance = distance;
        }

        public int getVertexid() {
            return vertexid;
        }

        public Double getDistance() {
            return distance;
        }

        public int compareTo(Vertex other) {
            return this.getDistance().compareTo(other.getDistance());
        }

        public boolean equals(Object o) {
            if (o instanceof Vertex) {
                Vertex v = (Vertex) o;
                return vertexid == v.vertexid && distance == v.distance;
            }
            return false;
        }
    }

    static class PathDistance {
        boolean containsNegativeCycle;
        double distance[];

        public PathDistance(int n) {
            containsNegativeCycle = false;
            distance = new double[n];
        }
    }

    static class Pair{
        int nodeindex;
        double nodeweight;

        Pair(int nodeindex, double nodeweight){
            this.nodeindex = nodeindex;
            this.nodeweight = nodeweight;
        }
    }

    public static ArrayList<LinkedList<Pair>> adjacencyListWeight(double g[][], int n){
        //function that takes in input an adjacency matrix and produces and adjacency list
        ArrayList<LinkedList<Pair>> adj_list = new ArrayList<LinkedList<Pair>>();

        //add the vertices
        for(int i=0; i<n; i++){
            adj_list.add(new LinkedList<Pair>());
        }

        //now add the edges
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i!=j || g[i][j] != Double.POSITIVE_INFINITY){
                    adj_list.get(i).add(new Pair(j, g[i][j]));
                }
            }
        }

        return adj_list;
    }

    public static double[][] adjacencyMatrix(ArrayList<LinkedList<Pair>> adjacenecyList, int n){
        double d[][] = new double[n][n];

        for(int i=0; i<n; i++){
            for(Pair l : adjacenecyList.get(i)){
                d[i][l.nodeindex] = l.nodeweight;
            }
        }

        return d;
    }

    public static ArrayList<LinkedList<Integer>>  adjacencyConversion(ArrayList<LinkedList<Pair>> adjacenecyList, int n){
        ArrayList<LinkedList<Integer>> d = new ArrayList<LinkedList<Integer>>();


        for(int i=0; i<n; i++){
            d.add(new LinkedList<Integer>());
            for(Pair l : adjacenecyList.get(i)){
                d.get(i).add(l.nodeindex);
            }
        }

        return d;
    }

    public static PathDistance dijkstra(ArrayList<LinkedList<Integer>> adj_list, double g[][], int n, int m, int source) {
        // g is the adjacency matrix
        // n is the number of nodes
        // m is the number of edges

        // initialize shortest path

        double d[] = new double[n];

        PathDistance dijkstraResult = new PathDistance(n);
        dijkstraResult.containsNegativeCycle = false;

        for (int i = 0; i < n; i++) {
            d[i] = Double.POSITIVE_INFINITY;
        }
        d[source] = 0;

        HashMap<Integer, Double> s = new HashMap<Integer, Double>();
        PriorityQueue<Vertex> q = new PriorityQueue<Vertex>();

        // initialize q
        for (int i = 0; i < n; i++) {
            q.add(new Vertex(i, d[i]));
        }

        Vertex u;

        while (!q.isEmpty()) {
            u = q.remove();
            // System.out.println(u.getVertexid() + "\t" + u.getDistance());
            s.put(u.getVertexid(), u.getDistance());

            //check all vertices which are adjacent to u
            for(Integer l : adj_list.get(u.getVertexid())){
                if (u.getDistance().doubleValue() + g[u.getVertexid()][l.intValue()] < d[l.intValue()] && s.containsKey(l.intValue()) == false) {
                    q.remove(new Vertex(l.intValue(), d[l.intValue()]));
                    d[l.intValue()] = u.getDistance().doubleValue() + g[u.getVertexid()][l.intValue()];
                    q.add(new Vertex(l.intValue(), d[l.intValue()]));
                }
            }
        }

        for (int i = 0; i < n; i++) {
            dijkstraResult.distance[i] = s.get(i);
        }

        return dijkstraResult;
    }

    public static PathDistance bellmanford(ArrayList<LinkedList<Integer>> adj_list, double g[][], int n, int m, int source) {
        // g is the adjacency matrix
        // n is the number of nodes
        // m is the number of edges

        // initialize shortest path

        PathDistance result = new PathDistance(n);

        double d[] = new double[n];

        for (int i = 0; i < n; i++) {
            d[i] = Double.POSITIVE_INFINITY;
        }
        d[source] = 0;

        LinkedList<Integer> l;

        for (int i = 0; i < n - 1; i++) {
            //relax all the edges
            for(int j=0; j<n; j++){
                l = adj_list.get(j);
                for(Integer edge : l){
                    if ( d[j] + g[j][edge] < d[edge]){
                        d[edge] = d[j] + g[j][edge];
                    }
                }
            }
        }
        // do one more round of relaxation
        // if we can relax once more, a negative cycle exists
        for (int j = 0; j < n; j++) {
            l = adj_list.get(j);
            for(Integer edge:l){
                if ((d[j] + g[j][edge]) < d[edge])
                    result.containsNegativeCycle = true;
            }
        }

        result.containsNegativeCycle = false;
        for (int i = 0; i < n; i++) {
            result.distance[i] = d[i];
        }

        return result;
    }

    public static double[][] johnson(ArrayList<LinkedList<Pair>> adj_list, int n, int m) {

        LinkedList<Pair> p = new LinkedList<Pair>();

        for(int i=0; i<n; i++){
            p.add(new Pair(i, 0));
        }

        adj_list.add(p);

        double result[][] = new double[n][n];
        double h[] = new double[n + 1];

        PathDistance bellmanfordresult;
        PathDistance dijkstraresult;

        bellmanfordresult = bellmanford(ShortestPaths.adjacencyConversion(adj_list, n+1), ShortestPaths.adjacencyMatrix(adj_list, n+1), n + 1, m, n);

        if (bellmanfordresult.containsNegativeCycle == true) {
            System.out.println("Negative Weight Cycle");
        } else {
            // set h[v] to be the vale computed by bellman ford
            for (int i = 0; i < n + 1; i++) {
                h[i] = bellmanfordresult.distance[i];
            }

            //now reweight all the edges

            for(int i=0; i<n; i++){
                for(Pair edge :adj_list.get(i)){
                    edge.nodeweight = edge.nodeweight + h[i] - h[edge.nodeindex];
                }
            }

            adj_list.remove(n);

            ArrayList<LinkedList<Integer>> adjList = ShortestPaths.adjacencyConversion(adj_list, n);
            double adjMatrix[][] = ShortestPaths.adjacencyMatrix(adj_list, n);
            // now run dijkstra for each vertex
            for (int i = 0; i < n; i++) {
                dijkstraresult = dijkstra(adjList, adjMatrix, n, m, i);
                for (int j = 0; j < n; j++) {
                    result[i][j] = dijkstraresult.distance[j] + h[i] - h[j];
                }
            }
        }

        //System.out.println("Johnson Algorithm");
        //ShortestPaths.printArray(result, n, n);
        return result;
    }

    public static void floydWarshall(double g[][], int n, int m) {
        double[][] distances;
        distances = Arrays.copyOf(g, n);

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]);
                }
            }

            if (distances[k][k] < 0.0) {
                System.out.println("Has Negative Cycle");
            }
        }

        //System.out.println("Floyd Warshall Algorithm");
        //ShortestPaths.printArray(distances, n, n);
    }

    public static void main(String[] args) {
        ShortestPaths f = new ShortestPaths();
        f.generateGraphs();
    }
}

У меня есть сомнения о том, насколько эффективным следующую часть кода :

                        q.remove(new Vertex(l.intValue(), d[l.intValue()]));
                        d[l.intValue()] = u.getDistance().doubleValue() + g[u.getVertexid()][l.intValue()];
                        q.add(new Vertex(l.intValue(), d[l.intValue()]));

За исключением использования биномиальной или кучи Фибоначчи, есть какие-то другие оптимизации, которые могут быть сделаны, чтобы этот код?



269
4
задан 12 апреля 2018 в 04:04 Источник Поделиться
Комментарии