WikiGalaxy
Shortest Path in Graphs: Dijkstra’s Algorithm
Dijkstra's Algorithm
Overview:
Dijkstra's algorithm is a popular method for finding the shortest path between nodes in a graph. It works by iteratively selecting the node with the smallest tentative distance, updating the distances to its neighbors, and marking it as visited.
Steps:
1. Initialize distances from the source to all vertices as infinite, except the source itself which is zero.
2. Use a priority queue to explore nodes with the smallest known distance.
3. Update the distance for each neighboring node, if a shorter path is found.
4. Repeat until all nodes are visited.
import java.util.*;
class Graph {
private int V;
private LinkedList[] adj;
class Edge {
int dest, weight;
Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList<>();
}
void addEdge(int src, int dest, int weight) {
adj[src].add(new Edge(dest, weight));
}
void dijkstra(int src) {
PriorityQueue pq = new PriorityQueue<>(V, new Node());
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
pq.add(new Node(src, 0));
dist[src] = 0;
while (!pq.isEmpty()) {
Node node = pq.poll();
for (Edge edge : adj[node.node]) {
if (dist[edge.dest] > dist[node.node] + edge.weight) {
dist[edge.dest] = dist[node.node] + edge.weight;
pq.add(new Node(edge.dest, dist[edge.dest]));
}
}
}
printSolution(dist);
}
void printSolution(int[] dist) {
System.out.println("Vertex \t Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i + " \t\t " + dist[i]);
}
class Node implements Comparator {
public int node, cost;
public Node() {}
public Node(int node, int cost) {
this.node = node;
this.cost = cost;
}
@Override
public int compare(Node n1, Node n2) {
return Integer.compare(n1.cost, n2.cost);
}
}
public static void main(String arg[]) {
Graph g = new Graph(5);
g.addEdge(0, 1, 9);
g.addEdge(0, 2, 6);
g.addEdge(0, 3, 5);
g.addEdge(0, 4, 3);
g.addEdge(2, 1, 2);
g.addEdge(2, 3, 4);
g.dijkstra(0);
}
}
Shortest Path in Graphs: Bellman-Ford Algorithm
Bellman-Ford Algorithm
Overview:
The Bellman-Ford algorithm computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm but more versatile, as it can handle graphs with negative weight edges.
Steps:
1. Initialize distances from the source to all vertices as infinite, except the source itself which is zero.
2. Relax all edges |V| - 1 times, where |V| is the number of vertices in the graph.
3. Check for negative-weight cycles.
import java.util.*;
class BellmanFord {
class Edge {
int src, dest, weight;
Edge() {
src = dest = weight = 0;
}
}
int V, E;
Edge edge[];
BellmanFord(int v, int e) {
V = v;
E = e;
edge = new Edge[e];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
void bellmanFord(BellmanFord graph, int src) {
int V = graph.V, E = graph.E;
int dist[] = new int[V];
for (int i = 0; i < V; ++i)
dist[i] = Integer.MAX_VALUE;
dist[src] = 0;
for (int i = 1; i < V; ++i) {
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
System.out.println("Graph contains negative weight cycle");
}
printArr(dist, V);
}
void printArr(int dist[], int V) {
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; ++i)
System.out.println(i + "\t\t" + dist[i]);
}
public static void main(String[] args) {
int V = 5;
int E = 8;
BellmanFord graph = new BellmanFord(V, E);
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;
graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;
graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;
graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;
graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;
graph.bellmanFord(graph, 0);
}
}
Shortest Path in Graphs: Floyd-Warshall Algorithm
Floyd-Warshall Algorithm
Overview:
The Floyd-Warshall algorithm is an all-pairs shortest path algorithm. It calculates the shortest paths between all pairs of vertices in a weighted graph with positive or negative edge weights (but with no negative cycles).
Steps:
1. Create a matrix of distances initialized to infinity, except for the diagonal which is zero.
2. Iterate over all pairs of vertices, updating the distance matrix by considering each vertex as an intermediate point.
class FloydWarshall {
final static int INF = 99999, V = 4;
void floydWarshall(int graph[][]) {
int dist[][] = new int[V][V];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
void printSolution(int dist[][]) {
System.out.println("Following matrix shows the shortest distances between every pair of vertices");
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
if (dist[i][j] == INF)
System.out.print("INF ");
else
System.out.print(dist[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int graph[][] = { { 0, 5, INF, 10 },
{ INF, 0, 3, INF },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 } };
FloydWarshall a = new FloydWarshall();
a.floydWarshall(graph);
}
}
Shortest Path in Graphs: A* Algorithm
A* Algorithm
Overview:
The A* algorithm is used for finding the shortest path in graphs. It is an extension of Dijkstra's algorithm with a heuristic that prioritizes paths that seem more promising, reducing the number of nodes explored.
Steps:
1. Maintain a priority queue of nodes to explore, starting with the initial node.
2. For each node, calculate the total cost as the sum of the path cost and a heuristic estimate to the goal.
3. Expand the node with the lowest total cost, updating paths and costs as necessary.
// Example implementation of A* algorithm is complex and usually involves specific heuristics
// such as Euclidean distance, which is not easily representable in a simple Java example.
// Instead, consider the pseudo-code or a more detailed implementation with a specific graph.
Shortest Path in Graphs: Johnson’s Algorithm
Johnson’s Algorithm
Overview:
Johnson's algorithm is used to find the shortest paths between all pairs of vertices in a sparse, weighted, directed graph. It uses both Dijkstra's and Bellman-Ford algorithms and is efficient for graphs with negative weights but without negative weight cycles.
Steps:
1. Add a new vertex connected to all other vertices with zero-weight edges.
2. Use Bellman-Ford to find the shortest path from the new vertex to each other vertex.
3. Re-weight the edges to eliminate negative weights.
4. Use Dijkstra's algorithm for each vertex.
// Johnson's algorithm involves multiple steps and is best explained with a detailed example and code.
// It is typically implemented using a combination of Bellman-Ford and Dijkstra's algorithms.
