为 TreeSet 实现自定义比较器时遇到问题（Dijkstra 的）

Question

我目前正在尝试并实现我自己的 Dijkstra 使用邻接列表的自定义 O(N.lgN) 解决方案。现在，如果您熟悉这个算法（很可能您是），我在为每个顶点存储元组时遇到了麻烦。如果您不知道我在说什么，请查看：http://qr.ae/LoESY

使用

可以轻松地将元组存储在 C++ 中

pair <int,int>.

无论如何，我找到了一个解决方案，并且在千方百计的情况下了解到，确实存在一个类似的 class，它被称为 'AbstractMap.SimpleEntry' Class。详情在这里：

既然您已经阅读了它，它的工作原理几乎与 pair<> 相同，并且足以将相邻边存储为元组中的键，将权重存储为元组中的值。

声明：Map.Entry pair= new AbstractMap.SimpleEntry(1,2);

现在我将所有输入都以元组的形式存储在每个向量的 ArrayList 中。我计划将输入的源元组添加到 TreeSet 中，并根据权重按升序对它们进行排序（对吗？）。但是，如果我只是将这些元组添加到 TreeSet，则会抛出一个错误：

Exception in thread "main" java.lang.ClassCastException:java.util.AbstractMap$SimpleEntry cannot be cast to java.lang.Comparable

现在我不知道如何为 TreeSet 实现自定义比较器，它按升序对我的值进行排序（在 Dijkstra 中，权重最小的边会先出现，对吗？）。另外，如果不能使用 TreeSet，您能否为我提供一个带有比较器的优先级队列？

即使您没有遵循，这也是我的代码。希望你会明白：

编辑代码根据以下答案

的建议编辑

package GRAPH;

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);
        OutputWriter out = new OutputWriter(System.out);
        //Initializing Graph
        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();
        for(int i=0;i<=v;i++)//Initializing rows for each vertex
        {
            gr.add(new ArrayList<AbstractMap.SimpleEntry<Integer, Integer>>());
        }
        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));
        }
        out.printLine(gr);
        System.out.printf("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);
        for(AbstractMap.SimpleEntry<Integer, Integer> pair: gr.get(s))//Error:Exception in thread "main" java.lang.ClassCastException: java.util.AbstractMap$SimpleEntry cannot be cast to java.lang.Comparable
        {
            ts.add(pair);
        }
        out.printLine(ts);
        {
            out.close();
        }
    }

    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
    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();
        }
    }
}

Enter Source1
[[], [2=3, 4=3], [3=4], [1=7], [3=2]]
[2=3]

编辑有效。谢谢@rgettman

Answer 1

您收到错误是因为 AbstractMap.SimpleEntry class 没有实现 Comparable。没有给定 Comparator 的 TreeSet 必须假定其元素是 Comparable，但它们不是。

您确定需要创建一个 Comparator 来告诉 TreeSet 如何排序元素是正确的。

创建您自己的 class 来实现 Comparator<AbstractMap.SimpleEntry<Integer, Integer>>。在compare方法中，提取权重并进行比较。

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());
    }
}

为 TreeSet 实现自定义比较器时遇到问题（Dijkstra 的）

Having trouble Implementing a Custom Comparator for a TreeSet (Dijkstra's)

java

algorithm

dijkstra

data-structures