This is for a school project; I have run into huge problems and I cannot find a clear solution.
abcdez a - 2 3 - - - b 2 - - 5 2 - c 3 - - - 5 - d - 5 - - 1 2 e - 2 5 1 - 4 z - - - 2 4 -
This is a two-dimensional array. Therefore, if you want to find the shortest path, it is from a, b, e, d, z = 7 and (a, b) = (b, a) - it will transfer you to a new line so that the next line of the path
Is there anyone who can help me implement Dijkstra's algorithm for this example? I would really appreciate it. (It seems to me that arrays are best suited, maps and sets confuse me a bit, the lists are manageable - although I’m ready to look into any solution at the moment)
[At least I’m not just breaking the source from the network. I really want to know these things ... It's just hard (>. <)]
Oh, starting point A, and ending point Z
Like most people, I do not find the concept of an algorithm difficult - I just see to get the right coding ... Help please?
Code example - a friend helped me a lot with this (although it was filled with data structures that are hard for me to find) I also tried to adapt the C ++ code from dreamincode.net/forums/blog/martyr2/index.php? showentry = 578 in java, but it is not so good ...
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))); } }