🌐 AI搜索 & 代理 主页
Skip to content

Commit 8ef0d49

Browse files
author
Lord-of-Algorithms
committed
Add Dijkstra’s algorithm to compute shortest paths
1 parent b4439df commit 8ef0d49

File tree

7 files changed

+593
-0
lines changed

7 files changed

+593
-0
lines changed

‎src/graph/dijkstra/DijkstraAlgorithm.java‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
package graph.dijkstra;
2+
3+
import graph.Vertex;
4+
import graph.dijkstra.graph.DijkstraGraph;
5+
6+
import java.util.*;
7+
8+
/**
9+
* Implements Dijkstra's algorithm for finding the shortest paths
10+
* from a single source vertex to all other vertices in a graph
11+
* with non-negative edge weights.
12+
*/
13+
public class DijkstraAlgorithm {
14+
15+
private final Map<Vertex, Vertex> predecessorMap;
16+
17+
public DijkstraAlgorithm() {
18+
predecessorMap = new HashMap<>();
19+
}
20+
21+
/**
22+
* Computes the shortest paths from the specified source vertex.
23+
*/
24+
public void computePaths(DijkstraGraph graph, Vertex source) {
25+
if (!graph.getVertices().contains(source)) {
26+
throw new IllegalArgumentException("Source vertex is not in the graph");
27+
}
28+
29+
Map<Vertex, Integer> distanceFromSourceMap = new HashMap<>();
30+
VertexDistancePriorityQueue pQueue = new VertexDistancePriorityQueue(graph.getVertexCount());
31+
32+
List<Vertex> vertices = graph.getVertices();
33+
for (Vertex v : vertices) {
34+
int initialDistance = v.equals(source) ? 0 : DijkstraGraph.INFINITY;
35+
distanceFromSourceMap.put(v, initialDistance);
36+
predecessorMap.put(v, null);
37+
pQueue.add(v, distanceFromSourceMap.get(v));
38+
}
39+
40+
while (!pQueue.isEmpty()) {
41+
Vertex closestToSource = pQueue.pollSmallest();
42+
List<Vertex> neighbors = graph.getNeighbors(closestToSource);
43+
44+
for (Vertex n : neighbors) {
45+
int currentDistance = distanceFromSourceMap.get(n);
46+
int edgeWeight = graph.getEdgeWeightBetween(closestToSource, n);
47+
// Safely compute an alternative path distance without risk of overflow
48+
int alternativeDistance = distanceFromSourceMap.get(closestToSource) + edgeWeight;
49+
if (alternativeDistance < currentDistance) {
50+
pQueue.update(n, alternativeDistance);
51+
distanceFromSourceMap.put(n, alternativeDistance);
52+
predecessorMap.put(n, closestToSource);
53+
}
54+
}
55+
}
56+
}
57+
58+
/**
59+
* Retrieves the shortest path from the source vertex
60+
* to the specified target vertex.
61+
*/
62+
public List<Vertex> getShortestPathTo(Vertex target) {
63+
List<Vertex> path = new ArrayList<>();
64+
path.add(target);
65+
Vertex predecessor = predecessorMap.get(target);
66+
while (predecessor != null) {
67+
path.add(predecessor);
68+
predecessor = predecessorMap.get(predecessor);
69+
}
70+
Collections.reverse(path); // Reverse the path to get the right order
71+
return path;
72+
}
73+
74+
/**
75+
* Resets the internal state of the algorithm, clearing stored predecessors.
76+
*/
77+
public void resetState() {
78+
predecessorMap.clear();
79+
}
80+
}

‎src/graph/dijkstra/VertexDistancePriorityQueue.java‎

Lines changed: 129 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,129 @@
1+
package graph.dijkstra;
2+
3+
import graph.Vertex;
4+
5+
import java.util.NoSuchElementException;
6+
7+
/**
8+
* A priority queue specifically designed for Dijkstra's algorithm that manages vertices according to their distances.
9+
* This implementation is simple and primarily for educational purposes to demonstrate the management of vertices in a
10+
* non-optimized priority queue. The queue maintains vertices in order of their distance from the source.
11+
* Each time a vertex is removed, it ensures the vertex with the smallest distance is selected next.
12+
*/
13+
class VertexDistancePriorityQueue {
14+
15+
/**
16+
* Inner class to hold vertex and its associated distance. This helps manage the mapping of vertices
17+
* to their current shortest distances as known during the execution of Dijkstra's algorithm.
18+
*/
19+
private static class VertexDistance {
20+
public final Vertex vertex;
21+
final int distance;
22+
23+
private VertexDistance(Vertex vertex, int distance) {
24+
this.vertex = vertex;
25+
this.distance = distance;
26+
}
27+
}
28+
29+
private final int maxSize;
30+
private final VertexDistance[] vertexDistances;
31+
private int currentSize;
32+
33+
/**
34+
* Constructs a priority queue with a specified maximum capacity.
35+
*
36+
* @param maxSize the maximum number of elements the queue can hold
37+
* @throws IllegalArgumentException if the specified maximum size is less than or equal to zero
38+
*/
39+
VertexDistancePriorityQueue(int maxSize) {
40+
if (maxSize <= 0) {
41+
throw new IllegalArgumentException("Maximum size must be greater than 0");
42+
}
43+
this.maxSize = maxSize;
44+
vertexDistances = new VertexDistance[maxSize];
45+
}
46+
47+
/**
48+
* Checks if the queue is empty.
49+
*
50+
* @return true if the queue has no elements, false otherwise
51+
*/
52+
boolean isEmpty() {
53+
return currentSize == 0;
54+
}
55+
56+
/**
57+
* Checks if the queue is full.
58+
*
59+
* @return true if the queue is at maximum capacity, false otherwise
60+
*/
61+
boolean isFull() {
62+
return currentSize == maxSize;
63+
}
64+
65+
/**
66+
* Adds a vertex along with its distance to the queue in a sorted order based on the distance.
67+
* If the queue is full, an IllegalStateException is thrown.
68+
*
69+
* @param vertex the vertex to add
70+
* @param distance the distance of the vertex from the source
71+
* @throws IllegalStateException if the queue is full
72+
*/
73+
void add(Vertex vertex, int distance) {
74+
if (isFull()) {
75+
throw new IllegalStateException("Queue is full");
76+
}
77+
int i;
78+
for (i = 0; i < currentSize; i++) {
79+
if (vertexDistances[i].distance <= distance) {
80+
// Break when find smaller distance
81+
break;
82+
}
83+
}
84+
// Move elements with smaller weight right on one position
85+
System.arraycopy(vertexDistances, i, vertexDistances, i + 1, currentSize - i);
86+
vertexDistances[i] = new VertexDistance(vertex, distance);
87+
currentSize++;
88+
}
89+
90+
/**
91+
* Polls and returns the vertex from the queue that has the smallest distance.
92+
* If the queue is empty, a NoSuchElementException is thrown.
93+
*
94+
* @return the vertex with the smallest distance
95+
* @throws NoSuchElementException if the queue is empty
96+
*/
97+
Vertex pollSmallest() {
98+
if (isEmpty()) {
99+
throw new NoSuchElementException("Queue is empty");
100+
}
101+
return vertexDistances[--currentSize].vertex;
102+
}
103+
104+
/**
105+
* Updates the distance of a specific vertex in the queue. If the vertex is not found,
106+
* a NoSuchElementException is thrown.
107+
*
108+
* @param vertex the vertex whose distance needs to be updated
109+
* @param newDistance the new distance of the vertex
110+
* @throws NoSuchElementException if the vertex is not found in the queue
111+
*/
112+
void update(Vertex vertex, int newDistance) {
113+
int index = -1;
114+
for (int i = 0; i < currentSize; i++) {
115+
if (vertexDistances[i].vertex.equals(vertex)) {
116+
index = i;
117+
break;
118+
}
119+
}
120+
if (index == -1) {
121+
throw new NoSuchElementException("Vertex not found");
122+
}
123+
// Removing the old vertexDistance
124+
System.arraycopy(vertexDistances, index + 1, vertexDistances, index, currentSize - index - 1);
125+
currentSize--;
126+
// Adding the new vertex-distance pair in sorted order
127+
add(vertex, newDistance);
128+
}
129+
}

‎src/graph/dijkstra/graph/DijkstraGraph.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package graph.dijkstra.graph;
2+
3+
import graph.Vertex;
4+
import graph.WeightedGraph;
5+
6+
import java.util.List;
7+
8+
/**
9+
* Defines the interface for a graph structure that can be used with Dijkstra's algorithm.
10+
*/
11+
public interface DijkstraGraph extends WeightedGraph {
12+
13+
// Represents a value considered as "infinite distance," used when there is no direct path between two vertices.
14+
// This value is set to half of Integer.MAX_VALUE to avoid arithmetic overflow when calculating distances.
15+
int INFINITY = Integer.MAX_VALUE / 2;
16+
17+
/**
18+
* Retrieves a list of all vertices in the graph.
19+
*/
20+
List<Vertex> getVertices();
21+
22+
/**
23+
* Retrieves a list of neighboring vertices to a specified vertex. Neighbors are
24+
* those vertices that are directly connected by an edge from the specified vertex.
25+
*/
26+
List<Vertex> getNeighbors(Vertex vertex);
27+
28+
/**
29+
* Retrieves the weight of the edge between two specified vertices.
30+
* If no edge exists, this method returns a value that signifies
31+
* no connection.
32+
*/
33+
int getEdgeWeightBetween(Vertex source, Vertex destination);
34+
35+
/**
36+
* Retrieves the count of vertices in the graph.
37+
*/
38+
int getVertexCount();
39+
}

‎src/graph/dijkstra/graph/DijkstraListGraph.java‎

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
package graph.dijkstra.graph;
2+
3+
import graph.Edge;
4+
import graph.Vertex;
5+
6+
import java.util.*;
7+
8+
/**
9+
* Implements the DijkstraGraph interface using an adjacency list representation.
10+
* This class supports directed graphs and is optimized for scenarios where the graph might be sparse.
11+
*/
12+
public class DijkstraListGraph implements DijkstraGraph {
13+
14+
private final Map<Vertex, List<Edge>> adjacencyList;
15+
private final List<Vertex> vertices;
16+
17+
/**
18+
* Constructs an empty DijkstraListGraph with no vertices or edges.
19+
*/
20+
public DijkstraListGraph() {
21+
adjacencyList = new HashMap<>();
22+
vertices = new ArrayList<>();
23+
}
24+
25+
/**
26+
* Adds a vertex to the graph. If the vertex is already in the graph, it does not add it again.
27+
*
28+
* @param vertex the vertex to add
29+
* @throws IllegalArgumentException if the vertex is null
30+
*/
31+
@Override
32+
public void addVertex(Vertex vertex) {
33+
if (vertex == null) {
34+
throw new IllegalArgumentException("Vertex cannot be null.");
35+
}
36+
if (!adjacencyList.containsKey(vertex)) {
37+
adjacencyList.put(vertex, new ArrayList<>());
38+
vertices.add(vertex);
39+
}
40+
}
41+
42+
/**
43+
* Adds or updates a directed edge from a source vertex to a destination vertex with a specified weight.
44+
*
45+
* @param source the source vertex of the edge
46+
* @param destination the destination vertex of the edge
47+
* @param weight the weight of the edge
48+
* @throws IllegalArgumentException if either vertex is null, if the vertices are the same,
49+
* or if one or both vertices do not exist in the graph,
50+
* or if the weight is negative.
51+
*/
52+
@Override
53+
public void setEdge(Vertex source, Vertex destination, int weight) {
54+
if (source == null || destination == null) {
55+
throw new IllegalArgumentException("Source or destination vertex cannot be null.");
56+
}
57+
58+
if (source == destination) {
59+
throw new IllegalArgumentException("Cannot add an edge from a vertex to itself.");
60+
}
61+
62+
if (!adjacencyList.containsKey(source) || !adjacencyList.containsKey(destination)) {
63+
throw new IllegalArgumentException("One or both vertices do not exist in the graph.");
64+
}
65+
66+
if (weight < 0) {
67+
throw new IllegalArgumentException("Edge weight cannot be negative.");
68+
}
69+
70+
List<Edge> edges = adjacencyList.get(source);
71+
72+
// Remove existing edge if it exists and add new one with updated weight
73+
replaceOrUpdateEdge(edges, source, destination, weight);
74+
}
75+
76+
/**
77+
* Replaces an existing edge between specified source and destination vertices or
78+
* adds a new edge if no existing edge is found.
79+
*/
80+
private void replaceOrUpdateEdge(List<Edge> edgeList, Vertex source, Vertex destination, int weight) {
81+
Edge existingEdge = findEdge(edgeList, source, destination);
82+
if (existingEdge != null) {
83+
edgeList.remove(existingEdge); // Remove old edge since Edge properties are final
84+
}
85+
edgeList.add(new Edge(source, destination, weight)); // Add new edge with the updated weight
86+
}
87+
88+
/**
89+
* Finds an edge between a specified source and destination vertex.
90+
*/
91+
private Edge findEdge(List<Edge> edges, Vertex source, Vertex destination) {
92+
for (Edge e : edges) {
93+
if (e.getSource().equals(source) && e.getDestination().equals(destination)) {
94+
return e;
95+
}
96+
}
97+
return null;
98+
}
99+
100+
@Override
101+
public List<Vertex> getVertices() {
102+
return Collections.unmodifiableList(vertices);
103+
}
104+
105+
@Override
106+
public List<Vertex> getNeighbors(Vertex vertex) {
107+
List<Vertex> neighbors = new ArrayList<>();
108+
List<Edge> edges = adjacencyList.get(vertex);
109+
for (Edge e : edges) {
110+
neighbors.add(e.getDestination());
111+
}
112+
return neighbors;
113+
}
114+
115+
@Override
116+
public int getEdgeWeightBetween(Vertex source, Vertex destination) {
117+
List<Edge> edges = adjacencyList.get(source);
118+
for (Edge e : edges) {
119+
if (e.getDestination().equals(destination)) {
120+
return e.getWeight();
121+
}
122+
}
123+
return INFINITY;
124+
}
125+
126+
@Override
127+
public int getVertexCount() {
128+
return vertices.size();
129+
}
130+
}

0 commit comments

Comments
 (0)