import java.util.*;
public class Study_Modified_BFS_Dijkstra_Queue {
private static final int spaceStepTime = 1;
private static final int dotStepTime = 3;
private static final String [] sourceMap = {
" ..... ",
" . . ........ ",
" .. ... ...... . ",
" . . ... .. ",
" .. ",
" ... ",
" .... .. . ",
" . . . . .. ",
" .. .... . .. ",
" ....... . ",
" ..... .. ",
". ....... . ",
"........ . . ",
" .. .. ",
" . ........ ",
" .. .......",
" .. ...... ...",
" .......... ",
" ... ... ",
" .... "
};
private static int width, height;
private static int [] [] stepCostMap;
private static int [] [] distanceMap;
private static int iterationsCount;
private static int comparisonsCount;
public static void main(String[] args) {
initializeMaps ();
iterationsCount = 0;
comparisonsCount = 0;
performDijkstraSearch (0, 0);
displayTravelMap ();
System .out .println ("Iterations Count = " + iterationsCount);
System .out .println ("Comparisons Count = " + comparisonsCount);
}
private static void initializeMaps () {
int k, l;
height = sourceMap .length;
width = sourceMap [0] .length ();
stepCostMap = new int [height] [width];
distanceMap = new int [height] [width];
for (k = 0; height > k; ++k) {
for (l = 0; width > l; ++l) {
switch (sourceMap [k] .charAt (l)) {
case '.':
stepCostMap [k] [l] = dotStepTime;
break;
default:
stepCostMap [k] [l] = spaceStepTime;
}
distanceMap [k] [l] = Integer .MAX_VALUE;
}
}
}
private static void displayTravelMap () {
int k, l;
for (k = 0; height > k; ++k) {
for (l = 0; width > l; ++l) {
System .out .print (String .format ("%3d", distanceMap [k] [l]));
}
System .out .println ();
}
System .out .println ();
}
private static void performDijkstraSearch (int x0, int y0) {
int k, x, y;
final int [] dx = {0, -1, 1, 0};
final int [] dy = {-1, 0, 0, 1};
Queue <QueueRecordClass> queue;
QueueRecordClass queueRecord, newQueueRecord;
queue = new PriorityQueue <> ();
newQueueRecord = new QueueRecordClass (x0, y0, 0);
newQueueRecord .setMapValue (distanceMap);
queue .add (newQueueRecord);
while (!queue .isEmpty ()) {
++iterationsCount;
queueRecord = queue .poll ();
// System .out .println (iterationsCount + " " + queueRecord .x + " " + queueRecord .y + " " + queueRecord .distance);
if (queueRecord .getMapValue (distanceMap) < queueRecord .distance) {
continue;
}
for (k = 0; 4 > k; ++k) {
x = queueRecord .x + dx [k];
y = queueRecord .y + dy [k];
if (0 > x || 0 > y || width <= x || height <= y) {
continue;
}
newQueueRecord = new QueueRecordClass (x, y, 0);
newQueueRecord .distance =
queueRecord .distance +
newQueueRecord .getMapValue (stepCostMap);
if (newQueueRecord .getMapValue (distanceMap) <= newQueueRecord .distance) {
continue;
}
newQueueRecord .setMapValue (distanceMap);
queue .add (newQueueRecord);
}
}
}
private static class QueueRecordClass implements Comparable <QueueRecordClass> {
int x, y, distance;
public QueueRecordClass (int x, int y, int distance) {
this .x = x;
this .y = y;
this .distance = distance;
}
public int getMapValue (int [] [] map) {
return map [y] [x];
}
public void setMapValue (int [] [] map) {
map [y] [x] = distance;
}
@Override
public int compareTo(QueueRecordClass arg) {
++comparisonsCount;
return distance - arg .distance;
}
}
}
