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)));
}
}
Simplest approach to find the shortest path in a 2D array would be to use BFS technique in the following way. Problem: Given a 2D array with values as 'S', 'D', '1' and '0'. Find the shortest distance from S to D avoiding all the obstacles.
Check for possible path in 2D matrix in C++We have to find if we can get a path from topleft corner to bottom-right corner. The matrix is filled with 0s and 1s. 0 indicates open area, 1 indicates blockage. Note that the top-left corner will always be 1.
A* is just like Dijkstra, the only difference is that A* tries to look for a better path by using a heuristic function which gives priority to nodes that are supposed to be better than others while Dijkstra's just explore all possible paths.
Most people prefer Dijkstra to DFS in pathfinding because Dijkstra is so accurate. Well, Dijkstra finds the shortest path from the starting point. DFS does not guarantee shortest path, it would just generate a path that visits very nodes in the graph. Dijkstra finds the shortest path for weighted graphs.
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);
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With