Java implements the shortest path algorithm (Dijkstra algorithm):
import java.util.*;
public class Dijkstra {
public static void main(String[] args) {
int[][] graph = {{0, 2, 4, 0, 0, 0},
{2, 0, 3, 5, 0, 0},
{4, 3, 0, 1, 7, 0},
{0, 5, 1, 0, 4, 2},
{0, 0, 7, 4, 0, 6},
{0, 0, 0, 2, 6, 0}};
int startNode = 0;
int[] dist = dijkstra(graph, startNode);
System.out.println(Arrays.toString(dist));
}
public static int[] dijkstra(int[][] graph, int startNode) {
int n = graph.length;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[startNode] = 0;
for (int i = 0; i < n - 1; i++) {
int u = findMinDist(dist, visited);
visited[u] = true;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist;
}
private static int findMinDist(int[] dist, boolean[] visited) {
int minDist = Integer.MAX_VALUE;
int minNode = -1;
for (int i = 0; i < dist.length; i++) {
if (!visited[i] && dist[i] < minDist) {
minDist = dist[i];
minNode = i;
}
}
return minNode;
}
}Python implements the shortest path algorithm (Dijkstra's algorithm):
import heapq
def dijkstra(graph, startNode):
n = len(graph)
dist = [float('inf')] * n
visited = [False] * n
dist[startNode] = 0
heap = [(0, startNode)]
while heap:
(d, u) = heapq.heappop(heap)
if visited[u]: continue
visited[u] = True
for v, w in graph[u]:
if not visited[v] and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
graph = [[(1, 2), (2, 4)],
[(0, 2), (2, 3), (3, 5)],
[(0, 4), (1, 3), (3, 1), (4, 7)],
[(1, 5), (2, 1), (4, 4), (5, 2)],
[(2, 7), (3, 4), (5, 6)],
[(3, 2), (4, 6)]]
startNode = 0
dist = dijkstra(graph, startNode)
print(dist)- Floyd algorithm
Floyd's algorithm is a dynamic programming algorithm for finding the shortest path between all pairs of nodes. The algorithm calculates the shortest path between all nodes by recursively recursing the distance between each pair of nodes.
Java code implementation:
public static int[][] floyd(int[][] graph) {
int n = graph.length;
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE && dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}Python code implementation:
import sys
def floyd(graph):
n = len(graph)
dist = [[0] * n for i in range(n)]
for i in range(n):
for j in range(n):
dist[i][j] = graph[i][j]
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] != sys.maxsize and dist[k][j] != sys.maxsize and dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist- Bellman-Ford Algorithm
The Bellman-Ford algorithm is a dynamic programming algorithm for solving the shortest path problem with negatively weighted edges. The algorithm calculates the shortest path from the origin to other nodes by performing a step-by-step relaxation operation on each edge.
Java code implementation:
public static int[] bellmanFord(int[][] graph, int start) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
for (int i = 0; i < n-1; i++) {
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
return dist;
}Python code implementation:
import sys
def bellman_ford(graph, start):
n = len(graph)
dist = [sys.maxsize] * n
dist[start] = 0
for i in range(n-1):
for u in range(n):
for v in range(n):
if graph[u][v] != 0 and dist[u] != sys.maxsize and dist[u] + graph[u][v] < dist[v]:
dist[v] = dist[u] + graph[u][v]
return distanalyze:
- Dijkstra's algorithm and Floyd's algorithm are suitable for shortest path problems without negative weight edges, while Bellman-Ford algorithm is suitable for shortest path problems with negative weight edges.
- The time complexity of Dijkstra's algorithm is O(V^2), where V is the number of nodes, but the time complexity can be optimized to O(E + VlogV) by using a priority queue, where E is the number of edges. The time complexity of Floyd's algorithm is O(V^3), and the space complexity is O(V^2). The time complexity of the Bellman-Ford algorithm is O(VE), where V is the number of nodes and E is the number of edges.
- In practical applications, Dijkstra's algorithm and Floyd's algorithm are usually used because of their low time complexity and wide application range. However, if there are negatively weighted edges, the Bellman-Ford algorithm must be used.
Both Java and Python can easily implement the shortest path algorithm, among which the Dijkstra algorithm is an algorithm based on greedy thinking, which can find the single-source shortest path in a directed or undirected graph. Both Java and Python have good libraries that support data structures, such as Arrays and PriorityQueue in Java, heapq and list in Python, etc., which can easily implement Dijkstra's algorithm.
In Java, we use an array dist to record the shortest distance from the starting point to each node, and a Boolean array visited to record whether each node has been visited. In each iteration, we select the unvisited node closest to the start and mark it as visited. We then iterate over all edges from this node, and if the edge's target node is not visited and the distance to the target node via this edge is smaller than the known shortest distance, update the shortest distance for that node. Finally, we return the dist array containing the shortest distance from the origin to each node.
In Python, we use a list dist to record the shortest distance from the starting point to each node, and a Boolean list visited to record whether each node has been visited. We also used Python's heapq module to implement a priority queue. In each iteration, we select the unvisited node closest to the start and mark it as visited. We then iterate over all edges from this node, and if the edge's target node is not visited and the distance to the target node via this edge is smaller than the known shortest distance, update the shortest distance for that node. Finally, we return the dist list, which contains the shortest distance from the origin to each node.