Hello ImDaGr3en
Dijkstra is a graph-algorithm which needs a graph as an Input. In order to create such a graph you need a suitable datastructure, which most commonly exists out of a combination of edge- and vertice-classes or an adjacency matrix. One possible implementation that I got to work for Processing is based on the following article:
https://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html
The following Processing code is based on the image in the attachment.
//-----Tab dijkstra-----
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
void setup(){
//create an array of vertices
Vertex[] vertices= {new Vertex("v1","A"),
new Vertex("v2","B"),
new Vertex("v3","C"),
new Vertex("v4","D"),
new Vertex("v5","E"),
new Vertex("v6","F"),
new Vertex("v7","G"),
new Vertex("v8","H")};
//save the vertices from the array into a List of vertices
List<Vertex> verticeList= new ArrayList<Vertex>();
for(int i=0; i<vertices.length; i++){
verticeList.add(vertices[i]);
}
//create a List of Edges between the vertices
List<Edge> edges= new ArrayList<Edge>();
edges.add(new Edge("e1",vertices[0],vertices[1],5));
edges.add(new Edge("e2",vertices[0],vertices[2],7));
edges.add(new Edge("e3",vertices[0],vertices[3],3));
edges.add(new Edge("e4",vertices[1],vertices[4],2));
edges.add(new Edge("e5",vertices[1],vertices[5],10));
edges.add(new Edge("e6",vertices[2],vertices[6],1));
edges.add(new Edge("e7",vertices[3],vertices[7],11));
edges.add(new Edge("e8",vertices[4],vertices[7],9));
edges.add(new Edge("e9",vertices[5],vertices[7],4));
edges.add(new Edge("e10",vertices[6],vertices[7],6));
//initialize a new Graph which is the basis for the Dijkstra Algorithm to work
Graph testGraph= new Graph(verticeList,edges);
DijkstraAlgorithm testAlgorithm= new DijkstraAlgorithm(testGraph);
//execute the Algorithm with the start Vertice being vertice[0] (simply the first one in the array)
testAlgorithm.execute(vertices[0]);
//print minimal Distances
println(testAlgorithm.distance.toString());
exit();
}
public class DijkstraAlgorithm {
private final List<Vertex> nodes;
private final List<Edge> edges;
private Set<Vertex> settledNodes;
private Set<Vertex> unSettledNodes;
private Map<Vertex, Vertex> predecessors;
private Map<Vertex, Integer> distance;
public DijkstraAlgorithm(Graph graph) {
// create a copy of the array so that we can operate on this array
this.nodes = new ArrayList<Vertex>(graph.getVertexes());
this.edges = new ArrayList<Edge>(graph.getEdges());
}
public void execute(Vertex source) {
settledNodes = new HashSet<Vertex>();
unSettledNodes = new HashSet<Vertex>();
distance = new HashMap<Vertex, Integer>();
predecessors = new HashMap<Vertex, Vertex>();
distance.put(source, 0);
unSettledNodes.add(source);
while (unSettledNodes.size() > 0) {
Vertex node = getMinimum(unSettledNodes);
settledNodes.add(node);
unSettledNodes.remove(node);
findMinimalDistances(node);
}
}
private void findMinimalDistances(Vertex node) {
List<Vertex> adjacentNodes = getNeighbors(node);
for (Vertex target : adjacentNodes) {
if (getShortestDistance(target) > getShortestDistance(node)
+ getDistance(node, target)) {
distance.put(target, getShortestDistance(node)
+ getDistance(node, target));
predecessors.put(target, node);
unSettledNodes.add(target);
}
}
}
private int getDistance(Vertex node, Vertex target) {
for (Edge edge : edges) {
if (edge.getSource().equals(node)
&& edge.getDestination().equals(target)) {
return edge.getWeight();
}
}
throw new RuntimeException("Should not happen");
}
private List<Vertex> getNeighbors(Vertex node) {
List<Vertex> neighbors = new ArrayList<Vertex>();
for (Edge edge : edges) {
if (edge.getSource().equals(node)
&& !isSettled(edge.getDestination())) {
neighbors.add(edge.getDestination());
}
}
return neighbors;
}
private Vertex getMinimum(Set<Vertex> vertexes) {
Vertex minimum = null;
for (Vertex vertex : vertexes) {
if (minimum == null) {
minimum = vertex;
} else {
if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
minimum = vertex;
}
}
}
return minimum;
}
private boolean isSettled(Vertex vertex) {
return settledNodes.contains(vertex);
}
private int getShortestDistance(Vertex destination) {
Integer d = distance.get(destination);
if (d == null) {
return Integer.MAX_VALUE;
} else {
return d;
}
}
/*
* This method returns the path from the source to the selected target and
* NULL if no path exists
*/
public LinkedList<Vertex> getPath(Vertex target) {
LinkedList<Vertex> path = new LinkedList<Vertex>();
Vertex step = target;
// check if a path exists
if (predecessors.get(step) == null) {
return null;
}
path.add(step);
while (predecessors.get(step) != null) {
step = predecessors.get(step);
path.add(step);
}
// Put it into the correct order
Collections.reverse(path);
return path;
}
}
//-----Tab Edge-----
public class Edge {
private final String id;
private final Vertex source;
private final Vertex destination;
private final int weight;
public Edge(String id, Vertex source, Vertex destination, int weight) {
this.id = id;
this.source = source;
this.destination = destination;
this.weight = weight;
}
public String getId() {
return id;
}
public Vertex getDestination() {
return destination;
}
public Vertex getSource() {
return source;
}
public int getWeight() {
return weight;
}
@Override
public String toString() {
return source + " " + destination;
}
}```
-----Tab Vertice-----
public class Vertex {
final private String id;
final private String name;
public Vertex(String id, String name) {
this.id = id;
this.name = name;
}
public String getId() {
return id;
}
public String getName() {
return name;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((id == null) ? 0 : id.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Vertex other = (Vertex) obj;
if (id == null) {
if (other.id != null)
return false;
} else if (!id.equals(other.id))
return false;
return true;
}
@Override
public String toString() {
return name;
}
}
-----Tab Graph-----
```import java.util.List;
public class Graph {
private final List<Vertex> vertexes;
private final List<Edge> edges;
public Graph(List<Vertex> vertexes, List<Edge> edges) {
this.vertexes = vertexes;
this.edges = edges;
}
public List<Vertex> getVertexes() {
return vertexes;
}
public List<Edge> getEdges() {
return edges;
}
}```
