需要对 Dijkstra 进行优化（独特算法）

Question

编辑：[已解决]

看看我在这个页面上的回答

好吧，在我努力在 JAVA 中实现 O(N.lgN) Dijkstra 解决方案时，我意识到首先，很难为相邻顶点和权重创建元组顶点。这可以很容易地在 C++ 中使用：

pair<int adv_vertex,int weight>

如果您不知道我在说什么，请查看此解决方案： http://qr.ae/LoESY

现在，我排除万难，在 JAVA 中找到了一个类似于 'pair<>' 的容器。例如 (1,1)，它声明为：

Map.Entry<Integer, Integer> pair=new AbstractMap.SimpleEntry<Integer,Integer>(1,1);

在此处阅读详细信息：

现在，我成功地使用这个 DataStructure 实现了 Dijkstra 算法。我使用了带有自定义比较器的 TreeSet。这非常类似于 PriorityQueue，它首先提取权重最小的顶点。这道题可以看作是扩展版的：

一切都完成后，我尝试解决了这个问题：

http://www.spoj.com/problems/EZDIJKST/

它清除了示例测试用例，但我在提交时收到了 TLE()TIme Limit Exceeded)。如此多地实现了前所未有的 Dijkstra。

这是获得 TLE 的代码：http://ideone.com/wAQfBu

这是我的实际 Dijkstra 实现和解释。我提交给SPOJ的那个就是没有注释和输出提示。你可能需要一段时间才能清醒过来。我试过在可能的地方和时间发表评论。

import java.io.*;
import java.util.*;

    /**
     * Created by Shreyans on 3/25/2015 at 7:26 PM using IntelliJ IDEA (Fast IO Template)
     */

    class DIJKSTA_TRY
    {
        public static void main(String[] args) throws Exception
        {
            InputReader in = new InputReader(System.in);
            //Initializing Graph

            //AbstractMap.SimpleEntry<Integer,Integer> is similar to pair<int a,int b> in C++

            List<ArrayList<AbstractMap.SimpleEntry<Integer,Integer>>>gr=new ArrayList<ArrayList<AbstractMap.SimpleEntry<Integer, Integer>>>();//AbstractMap.SimpleEntry<Integer,Integer> is similar to pair<int a,int b> in C++
            System.out.println("Enter no of Vertices");
            int v=in.readInt();
            System.out.println("Enter no of Edges");
            int e=in.readInt();
            Set<Integer>vertices=new HashSet<Integer>();
            for(int i=0;i<=v;i++)//Initializing rows for each vertex
            {
                vertices.add(i);
                gr.add(new ArrayList<AbstractMap.SimpleEntry<Integer, Integer>>());
            }
            vertices.remove(0);//Since 0 was added in advertantly
            System.out.println("Enter <Vertex> <Adjacent Vertex> <Weight>");
            for(int i=0;i<e;i++)
            {
                int a = in.readInt();
                int b = in.readInt();
                int c = in.readInt();
                gr.get(a).add(new AbstractMap.SimpleEntry<Integer, Integer>(b, c));
            }
            System.out.println("Enter Source");
            int s=in.readInt();
            Comparator<AbstractMap.SimpleEntry<Integer, Integer>> comparator=new WeightComparator();
            TreeSet<AbstractMap.SimpleEntry<Integer, Integer>>ts=new TreeSet<AbstractMap.SimpleEntry<Integer, Integer>>(comparator);
            int[]d=new int[v+1];
            Arrays.fill(d,Integer.MAX_VALUE);//Initial distance INFINITY
            d[s]=0;//Setting distance of source from source 0
            vertices.remove(s);
            for(AbstractMap.SimpleEntry<Integer, Integer> pair:gr.get(s))//Storing vertices adjacent to source
            {
                ts.add(pair);
                d[pair.getKey()]=pair.getValue();
            }
            while(!vertices.isEmpty()&&!ts.isEmpty())
            {
                AbstractMap.SimpleEntry<Integer, Integer> curr=ts.pollFirst();//Removing that element
                int V=curr.getKey();//Got adjacent vertex;
                int W=curr.getValue();//Got weight
                //vertices.remove();
                for(AbstractMap.SimpleEntry<Integer, Integer> pair:gr.get(V))//Now traversing vertives adjacent to V
                {
                    int v1=pair.getKey();
                    int w1=pair.getValue();
                    if(d[v1]>W+w1)//setting distance if shorted
                    {
                        d[v1]=W+w1;
                    }
                    ts.add(pair);//Adding to TreeSet
                }
                vertices.remove(V);//Removing V from Vertices set
            }
            System.out.println("Single Source Shortest Distance from Vertex "+(s)+" is:");
            for(int i=1;i<=v;i++)
            {
                System.out.println("Shortest Distance from Source Vertex "+s+" is: "+d[i]);
            }
        }

        static public class WeightComparator implements
                Comparator<AbstractMap.SimpleEntry<Integer, Integer>>
        {
            @Override
            public int compare(AbstractMap.SimpleEntry<Integer, Integer> one,
                               AbstractMap.SimpleEntry<Integer, Integer> two)
            {
                return Integer.compare(one.getValue(), two.getValue());
            }
        }
        //**FAST IO. THAT'S IT. NOTHING DOWN HERE**
        private static class InputReader
        {
            private InputStream stream;
            private byte[] buf = new byte[1024];
            private int curChar;
            private int numChars;
            private SpaceCharFilter filter;

            public InputReader(InputStream stream)
            {
                this.stream = stream;
            }

            public int read()
            {
                if (numChars == -1)
                    throw new InputMismatchException();
                if (curChar >= numChars)
                {
                    curChar = 0;
                    try
                    {
                        numChars = stream.read(buf);
                    } catch (IOException e)
                    {
                        throw new InputMismatchException();
                    }
                    if (numChars <= 0)
                        return -1;
                }
                return buf[curChar++];
            }

            public int readInt()
            {
                int c = read();
                while (isSpaceChar(c))
                    c = read();
                int sgn = 1;
                if (c == '-')
                {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do
                {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
            }

            public String readString()
            {
                int c = read();
                while (isSpaceChar(c))
                    c = read();
                StringBuilder res = new StringBuilder();
                do
                {
                    res.appendCodePoint(c);
                    c = read();
                } while (!isSpaceChar(c));
                return res.toString();
            }

            public double readDouble()
            {
                int c = read();
                while (isSpaceChar(c))
                    c = read();
                int sgn = 1;
                if (c == '-')
                {
                    sgn = -1;
                    c = read();
                }
                double res = 0;
                while (!isSpaceChar(c) && c != '.')
                {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, readInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                }
                if (c == '.')
                {
                    c = read();
                    double m = 1;
                    while (!isSpaceChar(c))
                    {
                        if (c == 'e' || c == 'E')
                            return res * Math.pow(10, readInt());
                        if (c < '0' || c > '9')
                            throw new InputMismatchException();
                        m /= 10;
                        res += (c - '0') * m;
                        c = read();
                    }
                }
                return res * sgn;
            }

            public long readLong()
            {
                int c = read();
                while (isSpaceChar(c))
                    c = read();
                int sgn = 1;
                if (c == '-')
                {
                    sgn = -1;
                    c = read();
                }
                long res = 0;
                do
                {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
            }

            public boolean isSpaceChar(int c)
            {
                if (filter != null)
                    return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }

            public String next()
            {
                return readString();
            }

            public interface SpaceCharFilter
            {
                public boolean isSpaceChar(int ch);
            }
        }

        private static class OutputWriter
        {
            private final PrintWriter writer;

            public OutputWriter(OutputStream outputStream)
            {
                writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
            }

            public OutputWriter(Writer writer)
            {
                this.writer = new PrintWriter(writer);
            }

            public void print(Object... objects)
            {
                for (int i = 0; i < objects.length; i++)
                {
                    if (i != 0)
                        writer.print(' ');
                    writer.print(objects[i]);
                }
            }

            public void printLine(Object... objects)
            {
                print(objects);
                writer.println();
            }

            public void close()
            {
                writer.close();
            }

            public void flush()
            {
                writer.flush();
            }
        }
    }

当我完成这个编码时，我真的很兴奋。我花了将近 5 个小时才找到所有资源并将它们放在一起来制作这个，但是当它无法及时清除测试用例时我感到非常失望。

有人可以建议另一种方式（也许是数据结构）/优化吗？

此外，这个特定算法的运行时间是多少？你把它改成了什么？（如果有）

Answer 1

您确定您的 IO 函数实际上比 Java 已经提供的更快吗？
代码似乎是 O((M + N) log N)，但常量很大。首先是因为您使用的是集合而不是优先级队列（如二进制堆），其次是因为您创建了许多实例的 AbstractMap.SimpleEntry 。然后因为你的数组列表列表，它也可能不是很快。

在 C++ 中，您经常可以摆脱它（但并非总是如此；在 C++ 中，Dijkstra 通常使用其优先级队列实现，而不是其集合实现）。对于Java，如果要做在线判断题，建议尽量少用已有的类，比如SimpleEntry。

我会做的是自己编写一个 binary heap 实现并使用它而不是你的集合，同时摆脱所有的 SimpleEntries 因为你对自己的堆实现有更多的控制，你可以只使用没有比较器的简单 class Pair { public int node; public int weight; }。

如果你不想走那么远，也许你可以先尝试用Java自己的PriorityQueue替换你的集合（注意使用正确的，O(log N) 删除方法！）。

Answer 2

这不是Dijstra的算法。 Dijkstra 算法枚举从源开始的所有 shortest 路径，而您的算法枚举从源开始的 all 路径，甚至包括那些包含循环的路径。

例如，考虑图表

1 <----> 2 <----> 3 <----> 4 <----> 5

Dijstra 将枚举以下路径：

[1]
[1,2]
[1,2,3]
[1,2,3,4]
[1,2,3,4,5]

而你的算法枚举

[1]
[1,2]
[1,2,1]
[1,2,3]
[1,2,1,2]
[1,2,3,2]
[1,2,3,4]
[1,2,1,2,1]
[1,2,1,2,3]
[1,2,3,2,1]
[1,2,3,2,3]
[1,2,3,4,3]
[1,2,3,4,5]

...如果图表再大一点，差异会更加显着。例如，考虑顶点集是整数的图，当且仅当 x + 1 = y 或 x = y + 1 时，两个顶点 x,y 相邻。设 0 为源，n 为目标。通过构造，从 0 到 n 的最短路径的长度为 n。 Dijkstra 将只访问从 -n 到 n 的所有节点一次。您的算法将访问所有长度最多为 n 的路径，其中有 2^n（包括 0,1,0,1,0,1,0,1,0,1,.... 等路径）。对于 n = 20，Dijkstra 将访问 41 条路径，而您的代码将访问大约一百万条路径！

因此，在您 fiddle 使用快速 I/O 例程之前，或尝试 fiddle 使用更快的树之前，请正确使用您的算法！

PS：除了速度慢之外，还有一些错误使您的实现不正确。例如，如果我们有一条长度为 n 的路径，并添加一个长度为 s 的步骤，则新路径的长度应为 n + s，而不是 s ...

Answer 3

终于好了！所以这是一个干净且（希望）FAST Dijkstra 的实现。

根据 IVlad 和其他一些人的建议，而不是使用：

AbstractMap.SimpleEntry

我创建了一个名为 'Node' 的自定义数据类型，它存储 2 个整数元组

Node x=new Node(AdjacentVertex,Weight)

我为此 'Node' class 实现了一个比较器，它根据分配的权重对其进行排序。重量更轻-> 优先级更高。

最后，我成功地实现了一个优先级队列，它根据比较器设置的上述顺序存储 'Node' 的对象。

Queue<Node> pq=new PriorityQueue<Node>(new Node());

我在 SPOJ 上获得了解决方案 AC（已接受）：http://www.spoj.com/status/EZDIJKST,bholagabbar/

这是 SPOJ 代码（与下面的代码相同，但具有更快的 IO 且没有提示语句）：http://ideone.com/p7u5vN

切入正题，这是我的最终、简单、'Proper' 和原始实现：

import java.util.*;

/**
 * Created by Shreyans on 4/21/2015 at 6:32 PM using IntelliJ IDEA (Fast IO Template)
 */

class DIJKSTRA
{
    public static void main(String[] args) throws Exception
    {
        Scanner sc=new Scanner(System.in);
        List<ArrayList<Node>> gr=new ArrayList<ArrayList<Node>>();//Initialising Adj list to store graph
        System.out.println("Enter Number of Vertices");
        int v=sc.nextInt();
        for(int i=0;i<=v;i++)
        {
            gr.add(new ArrayList<Node>());
        }
        System.out.println("Enter Number of Edges");
        int e=sc.nextInt();
        System.out.println("Enter <Vertex> <Adjacent Vertex> <Weight>");
        for(int i=0;i<e;i++)
        {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            gr.get(a).add(new Node(b,c));
        }//Built Graph
        System.out.println("Enter Source");
        int s=sc.nextInt();
        //int des=sc.nextInt();//Entering Destination
        Queue<Node> pq=new PriorityQueue<Node>(new Node());//Heap to extract value
        boolean[]checked=new boolean[v+1];//Keeping track of checked values
        int[]d=new int[v+1];//Keeping track of distances
        Arrays.fill(d,Integer.MAX_VALUE);
        d[s]=0;
        pq.clear();
        pq.offer(new Node(s,0));
        while(!pq.isEmpty())
        {
            Node x=pq.poll();
            int V=x.node;//Getting next node from heap
            int W=x.cost;//Getting cost
            checked[V]=true;
            for(int i=0;i<gr.get(V).size();i++)
            {
                Node z=gr.get(V).get(i);//Getting all adjacent Vertices
                if(!checked[(z.node)])//Not checking visited Vertices
                {
                    int v1=z.node;
                    int w1=z.cost;
                    if(d[v1]>W+w1)//Checking for min weight
                    {
                        d[v1]=W+w1;
                    }
                    pq.offer(new Node(v1,d[v1]));//Adding element to PriorityQueue
                }
            }
        }
        for(int i=1;i<=v;i++)//Printing Shortest Distances. Ignore ones with Integer.MAV_VALUE. Meh
        {
            if(d[i]==Integer.MAX_VALUE)
            {
                System.out.println("No Path connecting Source Vertex "+s+" to Vertex "+i);
            }
            else
            {
                System.out.println("Shortest distance from  Source Vertex "+s+" to Vertex "+i+" is: "+d[i]);
            }
        }
    }
}
class Node implements Comparator<Node>
{
    public int node;
    public int cost;

    public Node(){}

    public Node(int node, int cost)
    {
        this.node = node;
        this.cost = cost;
    }

    @Override
    public int compare(Node node1, Node node2)
    {
        if (node1.cost < node2.cost)
            return -1;
        if (node1.cost > node2.cost)
            return 1;
        return 0;
    }
}

谁能告诉我这个实现的确切时间和Space复杂性是什么？ 我正在做的项目需要这些细节。我的实施可以进一步改进吗？欢迎提出建议

需要对 Dijkstra 进行优化（独特算法）

Optimization for Dijkstra required (Unique Algorithm)

java

algorithm

optimization

dijkstra

data-structures