Skip to content

Latest commit

 

History

History
245 lines (186 loc) · 9.17 KB

2.4 - Pathfinding Algorithms.md

File metadata and controls

245 lines (186 loc) · 9.17 KB
Raw

Pathfinding Algorithms

Dijkstra's Algorithm (Adapted from Wikipedia, GIF)

  • Finds the shortest path from a start node to a goal node in a weighted, directed graph with non-negative edge weights.
  1. Assign every node a tentative distance value. Zero for the start node and infinity for all other nodes.
  2. Set the start node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes.
  3. For the current node, consider all of its neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. If the newly calculated tentative distance is smaller, assign the current node as the neighbor's previous node.
  4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
  5. If there are still unvisited nodes, select an unvisited node with the smallest tentative distance, set it as the new "current node" and go back to Step 3.
  6. Use the goal's previous node to recursively backtrack to the start node.
HashMap<Node, Node> Dijkstra(Node[] graph, Node start, Node goal) {
    // Keeps track of the previous node for a node in the path. Used to construct the path after
    // it is determined.
    HashMap<Node, Node> prev = new HashMap<>();

    // Queue that stores nodes in ascending order of distance.
    PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
        @Override
        public int compare(Node n1, Node n2) {
            return n1.dijkstraDistance - n2.dijkstraDistance;
        }
    });

    for (Node n : graph) {
        if (n != start) {
            n.dijkstraDistance = Integer.MAX_VALUE;
            prev.put(n, null);
        }
        queue.add(n);
    }
    start.dijkstraDistance = 0;

    while (!queue.isEmpty()) {
        Node current = queue.poll();  // get minimum distance node
        if (current == goal) return prev;

        for (Node neighbor : current.neighbors) {
            int altDistance = current.dijkstraDistance + distance(current, neighbor);
            if (altDistance < neighbor.dijkstraDistance) {
                neighbor.dijkstraDistance = altDistance;
                prev.put(neighbor, current);

                // Update position of node in queue.
                queue.remove(neighbor);
                queue.add(neighbor);
            }
        }
    }

    return null;  // no path found!
}

Time Complexity

  • Each node V can be adjacent to a maximum |V - 1| nodes.
  • Finding and updating the weight of each adjacent node in a binary heap is O(log |V|).
  • Therefore, updating all the adjacent nodes of one node is O(|V - 1| log |V|).
  • Hence, time complexity for updating for all nodes is O(|V| |V - 1| log |V|), which can be simplified to:
O(|E| log |V|)

where |E| represents the total number of edges in the graph.

Generally, Dijkstra's algorithm takes O(|E| * T_dk + |V| * T_em) where T_dk & T_em denote the complexities of the decrease-key and extract-minimum operation (both are O(log |V|) for a binary heap). If a graph is sparse, a binary heap implementation is preferred but if a graph is dense, an array implementation (O(|V|^2)) is preferred for the priority queue.

A* Search Algorithm (Adapted from Wikipedia)

  • Finds the shortest path from a start node to a goal node in a weighted, directed graph with non-negative edge weights.

The A* search algorithm is based on minimizing:

f(n) = g(n) + h(n)

where f(n) is the estimated distance of START to GOAL through n, g(n) is the known distance from START to n and h(n) is the heuristic distance from n to GOAL.

The heuristic must follow the the triangle inequality theorem i.e. |h(A) - h(b)| ≤ dist(A, B) for all nodes A, B and must never overestimate the actual minimal cost of reaching a goal.

Dijkstra's algorithm is a special case of A*, where h(n) = 0.

HashMap<Node, Node> AStar(Node[] graph, Node start, Node goal) {
    HashSet<Node> openSet = new HashSet<>();
    HashSet<Node> closedSet = new HashSet<>();

    openSet.add(start)

    HashMap<Node, Node> prev = new HashMap<>();
    HashMap<Node, Integer> gScore = new HashMap<>();
    HashMap<Node, Integer> fScore = new HashMap<>();

    for (Node n : graph) {
        gScore.put(n, Integer.MAX_VALUE);
        fScore.put(n, Integer.MAX_VALUE);
    }

    gScore.put(start, 0)
    fScore.put(start, 0 + heuristicEstimate(start, goal))

    while (!openSet.isEmpty()) {
        Node current = getMinimum(openSet, fScore);  // get node with lowest fScore value
        if (current == goal) return prev;

        openSet.remove(current);
        closedSet.add(current);

        for (Node neighbor : current.neighbors) {
            if (closedSet.contains(neighbor)) continue;
            if (!openSet.contains(neighbor)) openSet.add(neighbor);

            int altGScore = gScore.get(current) + distance(current, neighbor);
            if (altGScore < gScore.get(neighbor)) {
                prev.put(neighbor, current);
                gScore.put(neighbor, altGScore);
                fScore.put(neighbor, altGScore + heuristicEstimate(neighbor, goal));
            }
        }
    }

    return null;  // no path found!
}

Time Complexity

Since A* algorithm's runtime complexity is heavily dependent on the heuristic chosen, the worst case time complexity for an unbounded search space is:

O(b^d)

where b is the branching factor (i.e. average number of successors per state) and d is the depth of the solution.

Bellman-Ford Algorithm (Adapted from Wikipedia)

  • Finds the shortest path from a single source node to all other nodes in a weighted, directed graph, where edge weights may be negative. If there is a negative weight cycle, then the shortest distances are not calculated and the cycle is reported.
  1. Initialize distance for all nodes as infinite, except the source node, which is initialized as zero.
  2. Repeat the following |V| - 1 times:
    1. For each edge u, v, if dist[v] > dist[u] + weight(u, v), then dist[v] = dist[u] + weight(u, v).
  3. Repeat the following for each edge u, v:
    1. If dist[v] > ist[u] + weight(u, v), graph contains a negative weight cycle.
  • Step 3 is performed because Step 2 guarantees shortest distances only if the graph doesn't contain a negative weight cycle.
  • Unlike Dijkstra's algorithm, Bellman-Ford is capable of handling graphs with some negative weight edges.
class Graph {
    class Node {
        int id;
    }

    class Edge {
        int src;    // ID of source node
        int dest;   // ID of destination node
        int weight; // weight of edge
    }

    Node[] nodes;
    Edge[] edges;
}

int[] BellmanFord(Graph graph, int src) {
    int V = graph.node.length;
    int E = graph.edges.length;
    int[] dist = new int[V];  // distances to nodes

    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.edges[j].src;
            int v = graph.edges[j].dest;
            int weight = graph.edges[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.edges[j].src;
        int v = graph.edges[j].dest;
        int weight = graph.edges[j].weight;
        if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
            System.out.println("Graph contains negative weight cycle!");
            return null;
        }
    }

    return dist;
}

Time Complexity

O(|V| |E|)

Floyd-Warshall Algorithm (Adapted from Wikipedia)

  • Finds the shortest paths between all pairs of nodes in a weighted, directed graph, where edge weights may be negative but there are no negative weight cycles.
  1. Initialize the solution matrix as the same as the input graph matrix i.e. the shortest paths are initialized as the paths with no intermediate nodes.
  2. For every node k, consider it as the intermediate node for a path between u & v. Then, either:
    1. k is not an intermediate node in shortest path from u to v and the value of dist[u][v] is kept as it is.
    2. k is an intermediate node in the shortest path from u to v and the value of dist[u][v] is updated to dist[u][k] + dist[k][v].
int[][] FloydWarshall(int graph[][]) {
    int V = graph.length;
    int[][] dist = new int[V][V];
    int i, j, k;

    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    for (k = 0; k < V; k++) {
        for (u = 0; u < V; u++) {
            for (v = 0; v < V; v++) {
                if (dist[u][k] + dist[k][v] < dist[u][v])
                    dist[u][v] = dist[u][k] + dist[k][v];
            }
        }
    }

    return dist;
}

Time Complexity

O(|V|^3)