Floyd Warshall

public static void floyd() { for (int i = 1; i <= nInter; i++) { for (int j = 1; j <= nInter; j++) { for (int y = 1; y <= nInter; y++) { arnDelay[i][y] = Math.min(arnDelay[i][y],arnDelay[i][j] + arnDelay[j][y]); } } } }

I came up with this:

/**
 * UVA 10986
 *
 * Dijkstra's Algorithm
 *
 * The simpliest graph implementation is the adjacency matrix
 * but this isn't feasible for this problem since in the worst case
 * n = 19999 and there is no way you can have a 2d array of ints of size 19999 * 19999.
 *
 * My second approach used a map with an integer and linked list. This implementation
 * allows for bigger graphs but takes too long because you have to perform linear
 * searches to find vertices and to find the weight from v to i for every i.
 *
 * However; my program now successful solves the problem for the biggest input size
 * but not fast enough.
 */
package UVA;

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


public class email {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        graph g;
        int nCases;
        int nServers, nCables, nStart, nFinish;
        Scanner fin = new Scanner(new FileReader("email.txt"));
        //Scanner fin = new Scanner(System.in);
        int w, v, weight, nDist;
        int nCase = 1;

        nCases = fin.nextInt();

        for (int x = 0; x < nCases; x++) {
            nServers = fin.nextInt();
            nCables = fin.nextInt();
            nStart = fin.nextInt();
            nFinish = fin.nextInt();

            g = new graph(nServers);

            for (int i = 0; i < nCables; i++) {
                w = fin.nextInt();
                v = fin.nextInt();
                weight = fin.nextInt();
                g.addEdge(v, w, weight);
            }

            //g.outGraph();

            nDist = g.dijkstra(nStart, nFinish);

            System.out.println("Case #" + nCase + ": " + (nDist == -1 ? "unreachable" : nDist));
            nCase++;
        }

    }
}

class edge {

    int src;
    int dest;
    int weight;

    edge(int src, int dest, int w) {
        this.src = src;
        this.dest = dest;
        this.weight = w;
    }

    public String toString() {
        return dest + " ";
    }
}

class graph {

    int MAXV;
    HashMap<Integer, LinkedList<edge>> graph = new HashMap<Integer, LinkedList<edge>>(MAXV);

    graph(int v) {
        MAXV = v;
    }

    void addVertex(int v) {
        graph.put(v, new LinkedList<edge>());
    }

    void addEdge(int v, int w, int weight) {
        if (!graph.containsKey(v)) {
            addVertex(v);
        }

        if (!graph.containsKey(w)) {
            addVertex(w);
        }
        graph.get(v).add(new edge(v, w, weight));
        graph.get(w).add(new edge(w, v, weight));
    }

    void outGraph() {
        System.out.println(graph);
    }

    int dijkstra(int start, int finish) {
        boolean[] arbUsed = new boolean[MAXV + 1];
        int[] arnDist = new int[MAXV + 1];
        int v;
        int dist;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(MAXV + 1);

        v = start;

        Arrays.fill(arnDist, 2000000);
        arnDist[start] = 0;

        pq.add(v);

        while (!pq.isEmpty()) {
            v = pq.remove();
            arbUsed[v] = true;


            /**
             * for each vertex v adjacent to u, v not in S
            {
            if d(v) > d(u) + [u,v]    // a shorter distance exists
            {
            d(v) = d(u) + [u,v]
            π(v) = u
            add v to Q
            }
            }
             */
            try {
                Iterator<edge> nodes = graph.get(v).iterator();
                // update all shortest paths from v
                while (nodes.hasNext()) {
                    // find the weight from v to i
                    edge nextEdge = nodes.next();
                    int i = nextEdge.dest;

                    int next = nextEdge.weight;

                    dist = arnDist[v] + next;
                    if (arnDist[i] > dist) {
                        arnDist[i] = dist;
                        pq.add(i);
                    }

                }
            } catch (NullPointerException ex) {
                return -1;
            }
        }

        return arnDist[finish];

    }
}

Basically I use a Map which holds a LinkedList of neighboring nodes. It isn't very efficient because to find a neighbor we have to an 0(n) search through the linked list. It helps that the table is based on a Hashtable though so i get 0(1) access to any node in the map. This approach works but not fast enough.

It has to be with LinkedLists, ArrayLists and Vector use up too much memory. Either my input is too slow or my Dijkstra's implementation isn't fast enough. I think it is both of them actually. :/ Another problem is that the program has to do a linear search to check if the node already exists because if we add a node the second time, the contents of the liinked list will be gone. :/