Dijkstra 算法 - 邻接表和最小堆 - java
Dijksta's algorithm - Adjacency List and Min Heap - java
我已经使用这段代码来实现无向图并找到从节点 0 到 5 的最短路径。代码打印总距离如下：
源顶点：0 到顶点 5 的距离：10
但是，我希望打印最短路线，这应该是这样的：
0 - 4 - 5.
任何建议，请。
完成的代码如下：
import java.util.LinkedList;
public class DijkstraUsingMinHeap {
static class Edge {
int source;
int destination;
int weight;
public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
static class HeapNode{
int vertex;
int distance;
}
static class Graph {
int vertices;
LinkedList<Edge>[] adjacencylist;
Graph(int vertices) {
this.vertices = vertices;
adjacencylist = new LinkedList[vertices];
//initialize adjacency lists for all the vertices
for (int i = 0; i <vertices ; i++) {
adjacencylist[i] = new LinkedList<>();
}
}
public void addEdge(int source, int destination, int weight) {
Edge edge = new Edge(source, destination, weight);
adjacencylist[source].addFirst(edge);
edge = new Edge(destination, source, weight);
adjacencylist[destination].addFirst(edge); //for undirected graph
}
public void dijkstra_GetMinDistances(int sourceVertex){
int INFINITY = Integer.MAX_VALUE;
boolean[] SPT = new boolean[vertices];
// //create heapNode for all the vertices
HeapNode [] heapNodes = new HeapNode[vertices];
for (int i = 0; i <vertices ; i++) {
heapNodes[i] = new HeapNode();
heapNodes[i].vertex = i;
heapNodes[i].distance = INFINITY;
}
//decrease the distance for the first index
heapNodes[sourceVertex].distance = 0;
//add all the vertices to the MinHeap
MinHeap minHeap = new MinHeap(vertices);
for (int i = 0; i <vertices ; i++) {
minHeap.insert(heapNodes[i]);
}
//while minHeap is not empty
while(!minHeap.isEmpty()){
//extract the min
HeapNode extractedNode = minHeap.extractMin();
//extracted vertex
int extractedVertex = extractedNode.vertex;
SPT[extractedVertex] = true;
//iterate through all the adjacent vertices
LinkedList<Edge> list = adjacencylist[extractedVertex];
for (int i = 0; i <list.size() ; i++) {
Edge edge = list.get(i);
int destination = edge.destination;
//only if destination vertex is not present in SPT
if(SPT[destination]==false ) {
///check if distance needs an update or not
//means check total weight from source to vertex_V is less than
//the current distance value, if yes then update the distance
int newKey = heapNodes[extractedVertex].distance + edge.weight ;
int currentKey = heapNodes[destination].distance;
if(currentKey>newKey){
decreaseKey(minHeap, newKey, destination);
heapNodes[destination].distance = newKey;
}
}
}
}
//print SPT
printDijkstra(heapNodes, sourceVertex);
}
public void decreaseKey(MinHeap minHeap, int newKey, int vertex){
//get the index which distance's needs a decrease;
int index = minHeap.indexes[vertex];
//get the node and update its value
HeapNode node = minHeap.mH[index];
node.distance = newKey;
minHeap.bubbleUp(index);
}
public void printDijkstra(HeapNode[] resultSet, int sourceVertex){
for (int i = 0; i <vertices ; i++) {
if ( i == 5 ) {
System.out.println("Source Vertex: " + sourceVertex + " to vertex " + + i +
" distance: " + resultSet[i].distance);}
}
}
}
static class MinHeap{
int capacity;
int currentSize;
HeapNode[] mH;
int [] indexes; //will be used to decrease the distance
public MinHeap(int capacity) {
this.capacity = capacity;
mH = new HeapNode[capacity + 1];
indexes = new int[capacity];
mH[0] = new HeapNode();
mH[0].distance = Integer.MIN_VALUE;
mH[0].vertex=-1;
currentSize = 0;
}
public void insert(HeapNode x) {
currentSize++;
int idx = currentSize;
mH[idx] = x;
indexes[x.vertex] = idx;
bubbleUp(idx);
}
public void bubbleUp(int pos) {
int parentIdx = pos/2;
int currentIdx = pos;
while (currentIdx > 0 && mH[parentIdx].distance > mH[currentIdx].distance) {
HeapNode currentNode = mH[currentIdx];
HeapNode parentNode = mH[parentIdx];
//swap the positions
indexes[currentNode.vertex] = parentIdx;
indexes[parentNode.vertex] = currentIdx;
swap(currentIdx,parentIdx);
currentIdx = parentIdx;
parentIdx = parentIdx/2;
}
}
public HeapNode extractMin() {
HeapNode min = mH[1];
HeapNode lastNode = mH[currentSize];
// update the indexes[] and move the last node to the top
indexes[lastNode.vertex] = 1;
mH[1] = lastNode;
mH[currentSize] = null;
sinkDown(1);
currentSize--;
return min;
}
public void sinkDown(int k) {
int smallest = k;
int leftChildIdx = 2 * k;
int rightChildIdx = 2 * k+1;
if (leftChildIdx < heapSize() && mH[smallest].distance > mH[leftChildIdx].distance) {
smallest = leftChildIdx;
}
if (rightChildIdx < heapSize() && mH[smallest].distance > mH[rightChildIdx].distance) {
smallest = rightChildIdx;
}
if (smallest != k) {
HeapNode smallestNode = mH[smallest];
HeapNode kNode = mH[k];
//swap the positions
indexes[smallestNode.vertex] = k;
indexes[kNode.vertex] = smallest;
swap(k, smallest);
sinkDown(smallest);
}
}
public void swap(int a, int b) {
HeapNode temp = mH[a];
mH[a] = mH[b];
mH[b] = temp;
}
public boolean isEmpty() {
return currentSize == 0;
}
public int heapSize(){
return currentSize;
}
}
public static void main(String[] args) {
int vertices = 6;
Graph graph = new Graph(vertices);
int sourceVertex = 0;
graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 3);
graph.addEdge(1, 3, 2);
graph.addEdge(1, 2, 5);
graph.addEdge(2, 3, 7);
graph.addEdge(3, 4, 2);
graph.addEdge(4, 0, 4);
graph.addEdge(4, 1, 4);
graph.addEdge(4, 5, 6);
graph.dijkstra_GetMinDistances(sourceVertex);
}
}
提前致谢！
更新：更改为命名节点和边，并列出边。
这似乎有很多代码。这是另一个 Java 8+ 实现。
Dijkstra's algorithm完全在startAt方法中实现。
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public final class Graph {
private static final class Edge {
final String name;
final int weight;
Edge(String name, int weight) {
this.name = name;
this.weight = weight;
}
@Override
public String toString() {
return this.name + ":" + this.weight;
}
}
private static final class Node {
final String name;
Map<Node, Edge> edges = new HashMap<>();
Node[] path;
int pathWeight;
Node(String name) {
this.name = name;
}
}
private Map<String, Node> nodes = new HashMap<>();
public void addEdge(String sourceName, String destinationName, int weight, String edgeName) {
Node source = this.nodes.computeIfAbsent(sourceName, Node::new);
Node dest = this.nodes.computeIfAbsent(destinationName, Node::new);
Edge edge = new Edge(edgeName, weight);
source.edges.put(dest, edge);
dest.edges.put(source, edge);
}
public void startAt(String startNodeName) {
this.nodes.values().forEach(n -> n.path = null);
Node source = this.nodes.computeIfAbsent(startNodeName, Node::new);
source.path = new Node[] { source };
source.pathWeight = 0;
TreeSet<Node> pending = new TreeSet<>((a, b) -> Integer.compare(a.pathWeight, b.pathWeight));
pending.add(source);
while ((source = pending.pollFirst()) != null) {
for (Entry<Node, Edge> edge : source.edges.entrySet()) {
Node dest = edge.getKey();
int weight = source.pathWeight + edge.getValue().weight;
if (dest.path == null || weight < dest.pathWeight
|| (weight == dest.pathWeight && source.path.length + 1 < dest.path.length)) {
if (dest.path != null)
pending.remove(dest);
dest.path = Arrays.copyOf(source.path, source.path.length + 1);
dest.path[source.path.length] = dest;
dest.pathWeight = weight;
pending.add(dest);
}
}
}
}
public String getPath(String endNodeName) {
Node node = this.nodes.get(endNodeName);
if (node == null || node.path == null)
return "Unreachable";
String path = Arrays.stream(node.path).map(n -> n.name).collect(Collectors.joining(" - "));
String pathEdges = IntStream.range(1, node.path.length)
.mapToObj(i -> node.path[i - 1].edges.get(node.path[i]).toString())
.collect(Collectors.joining(" + "));
return path + " (distance: " + node.pathWeight + " = " + pathEdges + ")";
}
}
测试 1（原始边）
Graph graph = new Graph();
graph.addEdge("0", "1", 4, "A");
graph.addEdge("0", "2", 3, "B");
graph.addEdge("1", "2", 1, "C");
graph.addEdge("1", "3", 2, "D");
graph.addEdge("2", "3", 4, "E");
graph.addEdge("3", "4", 2, "F");
graph.addEdge("4", "5", 6, "G");
graph.startAt("0");
System.out.println(graph.getPath("5"));
输出 1
0 - 1 - 3 - 4 - 5 (distance: 14 = A:4 + D:2 + F:2 + G:6)
测试 2（更新边）
Graph graph = new Graph();
graph.addEdge("0", "1", 4, "A");
graph.addEdge("0", "2", 3, "B");
graph.addEdge("1", "3", 2, "C");
graph.addEdge("1", "2", 5, "D");
graph.addEdge("2", "3", 7, "E");
graph.addEdge("3", "4", 2, "F");
graph.addEdge("4", "0", 4, "G");
graph.addEdge("4", "1", 4, "H");
graph.addEdge("4", "5", 6, "I");
graph.startAt("0");
System.out.println(graph.getPath("5"));
输出 2
0 - 4 - 5 (distance: 10 = G:4 + I:6)
有关这两个测试的演示，请参阅 IDEONE。
我已经使用这段代码来实现无向图并找到从节点 0 到 5 的最短路径。代码打印总距离如下：
源顶点：0 到顶点 5 的距离：10
但是，我希望打印最短路线，这应该是这样的：
0 - 4 - 5.
任何建议，请。 完成的代码如下：
import java.util.LinkedList;
public class DijkstraUsingMinHeap {
static class Edge {
int source;
int destination;
int weight;
public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
static class HeapNode{
int vertex;
int distance;
}
static class Graph {
int vertices;
LinkedList<Edge>[] adjacencylist;
Graph(int vertices) {
this.vertices = vertices;
adjacencylist = new LinkedList[vertices];
//initialize adjacency lists for all the vertices
for (int i = 0; i <vertices ; i++) {
adjacencylist[i] = new LinkedList<>();
}
}
public void addEdge(int source, int destination, int weight) {
Edge edge = new Edge(source, destination, weight);
adjacencylist[source].addFirst(edge);
edge = new Edge(destination, source, weight);
adjacencylist[destination].addFirst(edge); //for undirected graph
}
public void dijkstra_GetMinDistances(int sourceVertex){
int INFINITY = Integer.MAX_VALUE;
boolean[] SPT = new boolean[vertices];
// //create heapNode for all the vertices
HeapNode [] heapNodes = new HeapNode[vertices];
for (int i = 0; i <vertices ; i++) {
heapNodes[i] = new HeapNode();
heapNodes[i].vertex = i;
heapNodes[i].distance = INFINITY;
}
//decrease the distance for the first index
heapNodes[sourceVertex].distance = 0;
//add all the vertices to the MinHeap
MinHeap minHeap = new MinHeap(vertices);
for (int i = 0; i <vertices ; i++) {
minHeap.insert(heapNodes[i]);
}
//while minHeap is not empty
while(!minHeap.isEmpty()){
//extract the min
HeapNode extractedNode = minHeap.extractMin();
//extracted vertex
int extractedVertex = extractedNode.vertex;
SPT[extractedVertex] = true;
//iterate through all the adjacent vertices
LinkedList<Edge> list = adjacencylist[extractedVertex];
for (int i = 0; i <list.size() ; i++) {
Edge edge = list.get(i);
int destination = edge.destination;
//only if destination vertex is not present in SPT
if(SPT[destination]==false ) {
///check if distance needs an update or not
//means check total weight from source to vertex_V is less than
//the current distance value, if yes then update the distance
int newKey = heapNodes[extractedVertex].distance + edge.weight ;
int currentKey = heapNodes[destination].distance;
if(currentKey>newKey){
decreaseKey(minHeap, newKey, destination);
heapNodes[destination].distance = newKey;
}
}
}
}
//print SPT
printDijkstra(heapNodes, sourceVertex);
}
public void decreaseKey(MinHeap minHeap, int newKey, int vertex){
//get the index which distance's needs a decrease;
int index = minHeap.indexes[vertex];
//get the node and update its value
HeapNode node = minHeap.mH[index];
node.distance = newKey;
minHeap.bubbleUp(index);
}
public void printDijkstra(HeapNode[] resultSet, int sourceVertex){
for (int i = 0; i <vertices ; i++) {
if ( i == 5 ) {
System.out.println("Source Vertex: " + sourceVertex + " to vertex " + + i +
" distance: " + resultSet[i].distance);}
}
}
}
static class MinHeap{
int capacity;
int currentSize;
HeapNode[] mH;
int [] indexes; //will be used to decrease the distance
public MinHeap(int capacity) {
this.capacity = capacity;
mH = new HeapNode[capacity + 1];
indexes = new int[capacity];
mH[0] = new HeapNode();
mH[0].distance = Integer.MIN_VALUE;
mH[0].vertex=-1;
currentSize = 0;
}
public void insert(HeapNode x) {
currentSize++;
int idx = currentSize;
mH[idx] = x;
indexes[x.vertex] = idx;
bubbleUp(idx);
}
public void bubbleUp(int pos) {
int parentIdx = pos/2;
int currentIdx = pos;
while (currentIdx > 0 && mH[parentIdx].distance > mH[currentIdx].distance) {
HeapNode currentNode = mH[currentIdx];
HeapNode parentNode = mH[parentIdx];
//swap the positions
indexes[currentNode.vertex] = parentIdx;
indexes[parentNode.vertex] = currentIdx;
swap(currentIdx,parentIdx);
currentIdx = parentIdx;
parentIdx = parentIdx/2;
}
}
public HeapNode extractMin() {
HeapNode min = mH[1];
HeapNode lastNode = mH[currentSize];
// update the indexes[] and move the last node to the top
indexes[lastNode.vertex] = 1;
mH[1] = lastNode;
mH[currentSize] = null;
sinkDown(1);
currentSize--;
return min;
}
public void sinkDown(int k) {
int smallest = k;
int leftChildIdx = 2 * k;
int rightChildIdx = 2 * k+1;
if (leftChildIdx < heapSize() && mH[smallest].distance > mH[leftChildIdx].distance) {
smallest = leftChildIdx;
}
if (rightChildIdx < heapSize() && mH[smallest].distance > mH[rightChildIdx].distance) {
smallest = rightChildIdx;
}
if (smallest != k) {
HeapNode smallestNode = mH[smallest];
HeapNode kNode = mH[k];
//swap the positions
indexes[smallestNode.vertex] = k;
indexes[kNode.vertex] = smallest;
swap(k, smallest);
sinkDown(smallest);
}
}
public void swap(int a, int b) {
HeapNode temp = mH[a];
mH[a] = mH[b];
mH[b] = temp;
}
public boolean isEmpty() {
return currentSize == 0;
}
public int heapSize(){
return currentSize;
}
}
public static void main(String[] args) {
int vertices = 6;
Graph graph = new Graph(vertices);
int sourceVertex = 0;
graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 3);
graph.addEdge(1, 3, 2);
graph.addEdge(1, 2, 5);
graph.addEdge(2, 3, 7);
graph.addEdge(3, 4, 2);
graph.addEdge(4, 0, 4);
graph.addEdge(4, 1, 4);
graph.addEdge(4, 5, 6);
graph.dijkstra_GetMinDistances(sourceVertex);
}
}
提前致谢！
更新：更改为命名节点和边，并列出边。
这似乎有很多代码。这是另一个 Java 8+ 实现。
Dijkstra's algorithm完全在startAt方法中实现。
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public final class Graph {
private static final class Edge {
final String name;
final int weight;
Edge(String name, int weight) {
this.name = name;
this.weight = weight;
}
@Override
public String toString() {
return this.name + ":" + this.weight;
}
}
private static final class Node {
final String name;
Map<Node, Edge> edges = new HashMap<>();
Node[] path;
int pathWeight;
Node(String name) {
this.name = name;
}
}
private Map<String, Node> nodes = new HashMap<>();
public void addEdge(String sourceName, String destinationName, int weight, String edgeName) {
Node source = this.nodes.computeIfAbsent(sourceName, Node::new);
Node dest = this.nodes.computeIfAbsent(destinationName, Node::new);
Edge edge = new Edge(edgeName, weight);
source.edges.put(dest, edge);
dest.edges.put(source, edge);
}
public void startAt(String startNodeName) {
this.nodes.values().forEach(n -> n.path = null);
Node source = this.nodes.computeIfAbsent(startNodeName, Node::new);
source.path = new Node[] { source };
source.pathWeight = 0;
TreeSet<Node> pending = new TreeSet<>((a, b) -> Integer.compare(a.pathWeight, b.pathWeight));
pending.add(source);
while ((source = pending.pollFirst()) != null) {
for (Entry<Node, Edge> edge : source.edges.entrySet()) {
Node dest = edge.getKey();
int weight = source.pathWeight + edge.getValue().weight;
if (dest.path == null || weight < dest.pathWeight
|| (weight == dest.pathWeight && source.path.length + 1 < dest.path.length)) {
if (dest.path != null)
pending.remove(dest);
dest.path = Arrays.copyOf(source.path, source.path.length + 1);
dest.path[source.path.length] = dest;
dest.pathWeight = weight;
pending.add(dest);
}
}
}
}
public String getPath(String endNodeName) {
Node node = this.nodes.get(endNodeName);
if (node == null || node.path == null)
return "Unreachable";
String path = Arrays.stream(node.path).map(n -> n.name).collect(Collectors.joining(" - "));
String pathEdges = IntStream.range(1, node.path.length)
.mapToObj(i -> node.path[i - 1].edges.get(node.path[i]).toString())
.collect(Collectors.joining(" + "));
return path + " (distance: " + node.pathWeight + " = " + pathEdges + ")";
}
}
测试 1（原始边）
Graph graph = new Graph();
graph.addEdge("0", "1", 4, "A");
graph.addEdge("0", "2", 3, "B");
graph.addEdge("1", "2", 1, "C");
graph.addEdge("1", "3", 2, "D");
graph.addEdge("2", "3", 4, "E");
graph.addEdge("3", "4", 2, "F");
graph.addEdge("4", "5", 6, "G");
graph.startAt("0");
System.out.println(graph.getPath("5"));
输出 1
0 - 1 - 3 - 4 - 5 (distance: 14 = A:4 + D:2 + F:2 + G:6)
测试 2（更新边）
Graph graph = new Graph();
graph.addEdge("0", "1", 4, "A");
graph.addEdge("0", "2", 3, "B");
graph.addEdge("1", "3", 2, "C");
graph.addEdge("1", "2", 5, "D");
graph.addEdge("2", "3", 7, "E");
graph.addEdge("3", "4", 2, "F");
graph.addEdge("4", "0", 4, "G");
graph.addEdge("4", "1", 4, "H");
graph.addEdge("4", "5", 6, "I");
graph.startAt("0");
System.out.println(graph.getPath("5"));
输出 2
0 - 4 - 5 (distance: 10 = G:4 + I:6)
有关这两个测试的演示，请参阅 IDEONE。