CODEWITHSUNDEEP
javaalgorithmgraphgraph-algorithm
user2288240
user2288240

Reputation: 1

Best way to traverse an almost complete undirected weighted graph

need help with an optimized solution for the following problem http://acm.ro/prob/probleme/B.pdf.

Depending on the cost i either traverse the graph using only new edges, or using only old edges, both of them work, but i need to pass test in a limited number of milliseconds, and the algorithm for the old edges is dragging me down.

I need a way to optimize this, any suggestions are welcome

EDIT: for safety reasons i am taking the algorithm down, i'm sorry, i'm new so I don't know what i need to do to delete the post now that it has answers

Upvotes: 0

Views: 749

Answers (2)

tmyklebu
tmyklebu

Reputation: 14215

My initial algorithmic suggestion relied on an incorrect reading of the problem. Further, a textbook breadth-first search or Dijkstra on a graph of this size is unlikely to finish in a reasonable amount of time. There's likely an early-termination trick that you can employ for large cases; the thread Niklas B. linked to suggests several (as well as some other approaches). I couldn't find an early-termination trick that I could prove worked.

These micro-optimisation notes are still relevant, however:

I'd suggest not using Java's built-in Queue container for this (or any other built-in Java containers for anything else in a programming contest). It turns your 4-byte int into a gargantual Integer structure. This is very probably where your blowup is coming from. You can use a 500000-long int[] to store the data in your queue and two ints for the front and back of the queue instead. In general, you want to avoid instantiating Objects in Java contest programming because of their overhead.

Likewise, I'd suggest representing the edges of the graph as either a single big int[] or a 500000-long int[][] to cut down on that piece of overhead.

Upvotes: 1

Mingtao Zhang
Mingtao Zhang

Reputation: 148

I only saw one queue in you code. That means you are searching from one direction only.

You may want to take a look at

Bidirectional Search

Upvotes: 0

Related Questions