NUHMAN.com

🔍 Find the Shortest Path Between Two Nodes in a Graph

Depending on the graph's characteristics, different algorithms are used:

AlgorithmHandles Negative Weights?Best Use CaseDijkstra❌ NoNon-negative weighted graphsBellman-Ford✅ YesGraphs with negative weightsA*❌ No (typically)Pathfinding with heuristicsBFS✅ N/A (unweighted only)Unweighted graphs

🧮 1. Dijkstra’s Algorithm (Non-negative Weights)

Use when: All edge weights are non-negative.

Time complexity: O((V + E) log V)

🔧 Java Implementation

java

public List<String> dijkstra(String start, String end) {
    Map<String, Integer> distances = new HashMap<>();
    Map<String, String> previous = new HashMap<>();
    PriorityQueue<Node> minHeap = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));
    List<String> path = new ArrayList<>();

    for (String vertex : adjVertices.keySet()) {
        distances.put(vertex, Integer.MAX_VALUE);
        previous.put(vertex, null);
    }
    distances.put(start, 0);
    minHeap.add(new Node(start, 0));

    while (!minHeap.isEmpty()) {
        Node currentNode = minHeap.poll();
        String currentVertex = currentNode.vertex;

        if (currentVertex.equals(end)) {
            while (currentVertex != null) {
                path.add(currentVertex);
                currentVertex = previous.get(currentVertex);
            }
            Collections.reverse(path);
            return path;
        }

        for (Edge edge : adjVertices.get(currentVertex)) {
            int newDist = distances.get(currentVertex) + edge.weight;
            if (newDist < distances.get(edge.to)) {
                distances.put(edge.to, newDist);
                previous.put(edge.to, currentVertex);
                minHeap.add(new Node(edge.to, newDist));
            }
        }
    }
    return path;
}

⚖️ 2. Bellman-Ford Algorithm (Handles Negative Weights)

Use when: There might be negative weights.

Time complexity: O(V * E)

🔧 Java Implementation

java

public Map<String, Integer> bellmanFord(String start) {
    Map<String, Integer> distances = new HashMap<>();
    for (String vertex : adjVertices.keySet()) {
        distances.put(vertex, Integer.MAX_VALUE);
    }
    distances.put(start, 0);

    for (int i = 1; i < adjVertices.size(); i++) {
        for (String u : adjVertices.keySet()) {
            for (Edge edge : adjVertices.get(u)) {
                if (distances.get(u) != Integer.MAX_VALUE &&
                    distances.get(u) + edge.weight < distances.get(edge.to)) {
                    distances.put(edge.to, distances.get(u) + edge.weight);
                }
            }
        }
    }

    // Check for negative-weight cycles
    for (String u : adjVertices.keySet()) {
        for (Edge edge : adjVertices.get(u)) {
            if (distances.get(u) != Integer.MAX_VALUE &&
                distances.get(u) + edge.weight < distances.get(edge.to)) {
                throw new RuntimeException("Graph contains a negative weight cycle");
            }
        }
    }

    return distances;
}

🌟 3. A* (A-Star) Algorithm

Use when: You have a good heuristic function to guide the search.

Time complexity: Depends on heuristic, often better than Dijkstra in practice.

🔧 Java Implementation

java

public List<String> aStar(String start, String end, Map<String, Integer> heuristic) {
    PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingInt(n -> n.f));
    Map<String, Integer> gScore = new HashMap<>();
    Map<String, String> cameFrom = new HashMap<>();
    List<String> path = new ArrayList<>();

    for (String v : adjVertices.keySet()) gScore.put(v, Integer.MAX_VALUE);
    gScore.put(start, 0);
    openSet.add(new Node(start, heuristic.getOrDefault(start, 0)));

    while (!openSet.isEmpty()) {
        Node current = openSet.poll();
        String currVertex = current.vertex;

        if (currVertex.equals(end)) {
            while (currVertex != null) {
                path.add(currVertex);
                currVertex = cameFrom.get(currVertex);
            }
            Collections.reverse(path);
            return path;
        }

        for (Edge edge : adjVertices.get(currVertex)) {
            int tentativeG = gScore.get(currVertex) + edge.weight;
            if (tentativeG < gScore.get(edge.to)) {
                cameFrom.put(edge.to, currVertex);
                gScore.put(edge.to, tentativeG);
                int fScore = tentativeG + heuristic.getOrDefault(edge.to, 0);
                openSet.add(new Node(edge.to, fScore));
            }
        }
    }
    return path;
}

🪜 4. Breadth-First Search (BFS) for Unweighted Graphs

Use when: All edges have equal weight.

Time complexity: O(V + E)

🔧 Java Implementation

java

public List<String> bfsShortestPath(String start, String end) {
    Queue<String> queue = new LinkedList<>();
    Map<String, String> parent = new HashMap<>();
    Set<String> visited = new HashSet<>();
    List<String> path = new ArrayList<>();

    queue.add(start);
    visited.add(start);
    parent.put(start, null);

    while (!queue.isEmpty()) {
        String current = queue.poll();
        if (current.equals(end)) {
            while (current != null) {
                path.add(current);
                current = parent.get(current);
            }
            Collections.reverse(path);
            return path;
        }
        for (Edge edge : adjVertices.get(current)) {
            if (!visited.contains(edge.to)) {
                queue.add(edge.to);
                visited.add(edge.to);
                parent.put(edge.to, current);
            }
        }
    }
    return path;
}

🧪 Sample Usage

java

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C");
        graph.addVertex("D"); graph.addVertex("E");

        graph.addEdge("A", "B", 1);
        graph.addEdge("A", "C", 4);
        graph.addEdge("B", "C", 2);
        graph.addEdge("B", "D", 5);
        graph.addEdge("C", "D", 1);
        graph.addEdge("D", "E", 3);

        List<String> path = graph.dijkstra("A", "E");
        System.out.println("Shortest path from A to E: " + path);
    }
}