在为TreeSet实现自定义比较器时遇到问题（Dijkstra’s）
我目前正在尝试使用Adjacency Lists实现我自己的Dijkstra定制O（N.lgN）解决方案。 现在，如果您熟悉此算法（很可能是您），我就无法存储每个Vertex的元组。 如果你不知道我在说什么，请联系： http ：//qr.ae/LoESY
元组可以很容易地用C ++存储
pair . 无论如何，我找到了解决方案，并且不顾一切地知道类似的类存在它被称为’AbstractMap.SimpleEntry’类。 详情如下：
https://stackoverflow.com/a/11253710/4258892
现在您已经阅读了它，它的工作方式几乎与pair 相同，并且足以将Adjacent Edge作为键存储，而Weight则作为元组中的Value存储。
声明：Map.Entry pair = new AbstractMap.SimpleEntry（1,2）;
现在，我将所有输入以元组的forms存储在每个向量的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>>gr=new ArrayList<ArrayList<AbstractMap.SimpleEntry>>();//AbstractMap.SimpleEntry is similar to pair 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>()); } System.out.println("Enter "); 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(b, c)); } out.printLine(gr); System.out.printf("Enter Source"); int s=in.readInt(); Comparator<AbstractMap.SimpleEntry> comparator=new WeightComparator(); TreeSet<AbstractMap.SimpleEntry>ts=new TreeSet<AbstractMap.SimpleEntry>(comparator); for(AbstractMap.SimpleEntry 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> { @Override public int compare(AbstractMap.SimpleEntry one, AbstractMap.SimpleEntry 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 '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 '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 '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 '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
您收到错误，因为AbstractMap.SimpleEntry类未实现Comparable 。 没有给出Comparator TreeSet必须假设它的元素是Comparable ，但它们不是。
你是对的，确定你需要创建一个Comparator ，告诉TreeSet如何订购元素。
创建自己的类，实现Comparator 。 在compare方法中，提取权重并进行比较。
public class WeightComparator implements Comparator> { @Override public int compare(AbstractMap.SimpleEntry one, AbstractMap.SimpleEntry two) { return Integer.compare(one.getValue(), two.getValue()); } }