Dijkstra algorithm for 2D array in Java

Question

This is for a school project; I'm running into a huge amount of trouble, and I can't seem to find a understandable solution.

   a b c d e z
 a - 2 3 - - -
 b 2 - - 5 2 -
 c 3 - - - 5 -
 d - 5 - - 1 2
 e - 2 5 1 - 4
 z - - - 2 4 -

That's the two dimensional array. So if you want to find the shortest path, its from a,b,e,d,z = 7, and (a,b) = (b,a) -- it takes you to the new row to for the row's adjacent paths

Is there anyone that can help me implement Dijkstra's algorithm for this example? I'd really appreciate it. (I seem to like arrays best, maps and sets confuse me a bit, lists are manageable -though I'm willing to look into any sort of solution at this point)

[At least I'm not just ripping off a source from the net. I actually wanna learn these things... It's just really hard (>.<)]

Oh, start point is A and end point is Z

---

As most people, I don't find the concept of the algorithm difficult -- I just can see to get the coding right... Help please?

Sample code-- a friend helped me with this a lot (though its filled with data structures that I find difficult to follow) I"ve also tried adapting the C++ code from dreamincode.net/forums/blog/martyr2/index.php?showentry=578 into java, but that didn't go so well ...

import java.util.*;

public class Pathy{

    private static class pathyNode{
        public final String name;
        public Map<pathyNode, Integer> adjacentNodes;

        public pathyNode(String n){
            name = n;
            adjacentNodes = new HashMap<pathyNode, Integer>();
        }

    }

    //instance variables

    //constructors

    //accessors

    //methods
    public static ArrayList<pathyNode> convert(int[][] inMatrix){
        ArrayList<pathyNode> nodeList = new ArrayList<pathyNode>();
        for(int i = 0; i < inMatrix.length; i++){
            nodeList.add(new pathyNode("" + i));
        }
        for(int i = 0; i < inMatrix.length; i++){
            for(int j = 0; j < inMatrix[i].length; j++){
                if(inMatrix[i][j] != -1){
                    nodeList.get(i).adjacentNodes.put(nodeList.get(j),
                            new Integer(inMatrix[i][j]));
                }
            }
        }
        return nodeList;
    }

    public static Map<pathyNode, Integer> Dijkstra(ArrayList<pathyNode> inGraph){
        Set<pathyNode> visited = new HashSet<pathyNode>();
        visited.add(inGraph.get(0));
        pathyNode source = inGraph.get(0);
        Map answer = new TreeMap<pathyNode, Integer>();
        for(pathyNode node : inGraph){
            dijkstraHelper(visited, 0, source, node);
            answer.put(node, dijkstraHelper(visited, 0, source, node));
        }
        return answer;
    }

    private static int dijkstraHelper(Set<pathyNode> visited, int sum, pathyNode start, pathyNode destination){
        Map<pathyNode, Integer> adjacent = new HashMap<pathyNode, Integer>();

        for(pathyNode n : visited){
            for(pathyNode m: n.adjacentNodes.keySet()){
                if(adjacent.containsKey(m)){
                    Integer temp = n.adjacentNodes.get(m);
                    if(temp < adjacent.get(m)){
                        adjacent.put(m, temp);
                    }
                }
                else{
                    adjacent.put(m, n.adjacentNodes.get(m));
                }
            }
        }

        Map<pathyNode, Integer> adjacent2 = new HashMap<pathyNode, Integer>();
        Set<pathyNode> tempSet = adjacent.keySet();
        tempSet.removeAll(visited);
        for(pathyNode n: tempSet){
            adjacent2.put(n, adjacent.get(n));
        }
        adjacent = adjacent2;
        Integer min = new Integer(java.lang.Integer.MAX_VALUE);
        pathyNode minNode = null;

        for(pathyNode n: adjacent.keySet()){
            Integer temp = adjacent.get(n);
            if(temp < min){
                min = temp;
                minNode = n;
            }
        }
        visited.add(minNode);
        sum += min.intValue();
        sum = dijkstraHelper(visited, sum, start, destination);
        return sum;
    }

    //main
    public static void main(String[] args){

        int[][] input = new int[][] { {-1, 2, 3, -1, -1, -1},
                          {2, -1, -1, 5, 2, -1},
                          {3, -1, -1, -1, 5, -1},
                          {-1, 5, -1, -1, 1, 2},
                          {-1, 2, 5, 1, -1, 4},
                          {-1, -1, -1, 2, 4, -1},
                        };
                        //-1 represents an non-existant path

        System.out.println(Dijkstra(convert(input)));
    }
}

Solution

The representation that you are calling 2D array, is the Adjacency matrix representation of a graph and the problem you are trying to solve is an instance of 'Single-Source Shortest Paths' problem. Dijkstra's algorithm is designed to solve this type of problem. This might be helpful http://renaud.waldura.com/doc/java/dijkstra/. Download the code from the site and read the documentation. Basically you will need to write code similar to following

    RoutesMap map = map =  new DenseRoutesMap(5);
    map.addDirectRoute(City.A, City.B, 2);
    map.addDirectRoute(City.A, City.C, 3);
    map.addDirectRoute(City.B, City.A, 2);
    map.addDirectRoute(City.B, City.D, 5);
    map.addDirectRoute(City.B, City.D, 2);
    ...
    DijkstraEngine engine = new DijkstraEngine(map);
    int distance = engine.getShortestDistance(City.F);

Comments

[Stan]

Unfortunately, that site doesn't help me much. It doesn't deal with 2D arrays like I need it too... Does anyone else have a solution/ suggestion?

[William Brendel]

@Babar: Nice way of nudging him in the right direction without spilling all the beans. +1

[Jared]

Very nice, TA-like answer :) +1.

[Jared]

@Stan - Babar is encouraging you to think about implementing the algorithm, not the data structures. That's definitely a better approach to learning the solution.

[Stan]

thanks guys-- I'll definitely look into the reading and implementation soon enough... Though it'd be mostly next week -- this week I'm mostly occupied. I'll post back when I get the chance/ time ;) !!