EDIT: [SOLVED]
HAVE A LOOK AT MY ANSWER ON THIS PAGE
Alright so in my endeavour to implement a O(N.lgN) Dijkstra solution in JAVA, i realised that first of all, it was hard to create tuples for Adjacent vertices and Weights for each vertex. This can easiy be done in C++ using:
pair<int adv_vertex,int weight>
If you have no idea what i'm talking about, have a look at this solution: http://qr.ae/LoESY
Now, against all odds, i found a container similar to 'pair<>' in JAVA. As an example for(1,1), its declared as:
Map.Entry<Integer, Integer> pair=new AbstractMap.SimpleEntry<Integer,Integer>(1,1);
Read the details here: https://stackoverflow.com/a/11253710/4258892
Now, I succeeded in implementing a Dijkstra Algorithm using this DataStructure. I used a TreeSet with a custom comparator. This pretty much works like a PriorityQueue which extracts vertices having least weight first. This question can be considered as an extended version of:
Having trouble Implementing a Custom Comparator for a TreeSet (Dijkstra's)
After everthing was done, I tried my hand at this problem:
http://www.spoj.com/problems/EZDIJKST/
It clears the sample testcases but I get a TLE()TIme Limit Exceeded) on submission. So much for implementing a Dijkstra like no one ever has.
Here is the code that got TLE: http://ideone.com/wAQfBu
And here is my actual Dijkstra implementation with Explanation. The one I submitted to SPOJ is just without the comments and the output prompts. It could take a while for you to get your head around. I've tried commenting where and when possible.
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();
}
}
}
I was really stoked when i completed coding this. Took me almost 5 hours to find all the resources and put them together to make this but was highly disappointed when it couldn't clear the testcases in time.
Could someone please Suggest another way (Maybe a Data-Structure)/Optimization?
Also, what is the running time of this particular algo? What have you changed it to? (If you have)
