Это для школьного проекта; Я сталкиваюсь с огромными проблемами, и я не могу найти понятного решения.Алгоритм Dijkstra для 2D-массива в Java
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 -
Это двухмерный массив. Поэтому, если вы хотите найти кратчайший путь, его из a, b, e, d, z = 7 и (a, b) = (b, a) - он приведет вас к новой строке для смежного соседнего ряда пути
Есть ли кто-нибудь, кто может помочь мне реализовать алгоритм Дейкстры для этого примера? Я бы очень признателен. (Кажется, мне нравятся массивы, карты и наборы немного путают меня, списки управляемы - хотя я готов заглянуть в любое решение на данный момент)
[По крайней мере, я не просто срываю источник из сети. Я на самом деле хочу узнать эти вещи ... Это просто очень трудно (>. <)]
О, начать точка А и конечная точка Z
Как и большинство людей, я не нахожу концепция алгоритма сложная - я просто вижу, чтобы получить право кодирования ... Помогите пожалуйста?
Пример кода - мне очень помог друг с другом (хотя он заполнен структурами данных, которые мне кажутся трудными) Я также попытался адаптировать код C++ из dreamincode.net/forums/blog/martyr2/ index.php? showentry = 578 в Java, но это не так хорошо ...
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)));
}
}
К сожалению, этот сайт мне не очень помогает. Он не касается 2D-массивов, как мне это нужно ... Есть ли у кого-нибудь еще решение/предложение? – Stan
Я обновил свой ответ и добавил образец кода. – Babar
@Babar: Хороший способ подталкивать его в правильном направлении, не проливая все бобы. +1 –