In the previous article, we discussed two graph traversal algorithms, BFS and DFS, which can be used for graph search. These algorithms are examples of uninformed search, deployable in any scenario without prior information about the graph. In this article, we will extend the discussion by introducing uninformed search on weighted graphs, Dijkstra's algorithm, and informed search with prior knowledge about the graph, A* Search.

Dijkstra's Algorithm

Dijkstra's algorithm is an uninformed search algorithm that works on a weighted graph, which has corresponding weights assigned to its edges. The weights can represent the cost of traveling from one node to another, such as time, and the algorithm attempts to minimize the total cost of reaching the destination. Thus, the algorithm may take more steps to reach the destination if the total cost is lower than that of other paths. The primary strategy of Dijkstra's algorithm is to keep updating the lowest cost to reach each node as we explore vertices, prioritizing those with the lowest possible cost. Below is the implementation of Dijkstra's algorithm applied to an AdjacencyMatrix, modified to include weight values.

void Dijkstra (WeightedAdjacencyMatrix graph, int start, int end) {
    cout << "Look for path between " << start << " to " << end << endl;
    // Initial Estimate
    vector<int> estimates(graph.mat.size(), 100);
    unordered_set<int> explored;
    int current = start;
    estimates[start] = 0;
    explored.insert(start);
 
    while (current != end) {
        cout << "To Explore: " << current << endl;
        vector<int> edges = graph.mat[current];
        // Update the estimate
        for (int e = 0; e < edges.size(); e++) {
            int new_estimate = estimates[current] + edges[e];
            if (edges[e] != 0 && new_estimate < estimates[e]) {
                estimates[e] = new_estimate;
            }
        }
        // Choose the unexplored minimum from estimates and explore
        int min = 200;
        int min_id;
        for (int i = 0; i < estimates.size(); i++) {
            if (explored.find(i) == explored.end()) {
                if (estimates[i] < min) {
                    min = estimates[i];
                    min_id = i;
                }
            }
        }
        current = min_id;
        explored.insert(min_id);
    }
 
    // Computed Cost
    cout << "Min cost is " << estimates[end] << endl;
};

I highly recommend checking out the beautiful visualization in How Dijkstra's Algorithm Works by Spanning Tree (2020). Since there is no infinity value in C++, I used 100 as the upper bound, assuming that the weights range between 0 and 10. It is important to note that the algorithm does not work when any edge has a negative cost because it would require visiting all the nodes to confirm there is no path that reduces the cost. Despite its simplicity, the algorithm can identify the shortest path to the destination node in a weighted graph without relying on other information. From the above code, we can deduce that the time and space complexities are $O(V^2)$ and $O(V)$, respectively.

A* Search

One drawback of Dijkstra's algorithm is that the search can propagate in all directions, including away from the destination vertex, unless the weights of the immediate edges are the lowest. If we have information about the direction of the destination, we can guide the search to favor the correct direction and reliably find the shortest path. A* search is an extension of BFS or Dijkstra's algorithm, depending on the presence of weights, and uses prior knowledge about the graph, called a heuristic function, to measure the degree of closeness to the goal. Typically, heuristics include Euclidean or Manhattan distances, which can be calculated using the coordinates of the vertices of a graph.

The strategy for choosing the next vertex to explore is the same as in Dijkstra's algorithm: selecting the one with the lowest cost estimate. In A* search, however, we add the heuristic value to the cost estimate to guide the search in the right direction.

void AStarSearch (WeightedAdjacencyMatrix graph, int start, int end, vector<int> heuristics) {
    cout << "Look for path between " << start << " to " << end << endl;
    // Initial Estimate
    vector<int> estimates(graph.mat.size(), 100);
    unordered_set<int> explored;
    int current = start;
    estimates[start] = 0;
    explored.insert(start);
 
    while (current != end) {
        cout << "To Explore: " << current << endl;
        vector<int> edges = graph.mat[current];
        // Update the estimate
        for (int e = 0; e < edges.size(); e++) {
            int new_estimate = estimates[current] + edges[e];
            if (edges[e] != 0 && new_estimate < estimates[e]) {
                estimates[e] = new_estimate;
            }
        }
        // Choose the unexplored minimum from estimates and explore
        int min = 200;
        int min_id;
        for (int i = 0; i < estimates.size(); i++) {
            if (explored.find(i) == explored.end()) {
                if (estimates[i] + heuristics[i] < min) {
                    min = estimates[i] + heuristics[i];
                    min_id = i;
                }
            }
        }
        current = min_id;
        explored.insert(min_id);
    }
    // Computed Cost
    cout << "Min cost is " << estimates[end] << endl;
};
 
int main () {
    WeightedAdjacencyMatrix mat(7);
    mat.addEdge(0, 2, 3);
    mat.addEdge(0, 5, 2);
    mat.addEdge(1, 3, 1);
    mat.addEdge(1, 4, 2);
    mat.addEdge(1, 5, 6);
    mat.addEdge(1, 6, 2);
    mat.addEdge(2, 3, 4);
    mat.addEdge(2, 4, 1);
    mat.addEdge(2, 5, 2);
    mat.addEdge(4, 5, 3);
    mat.addEdge(5, 6, 5);
    int hValues[] = {4, 0, 3, 1, 2, 3, 1};
    vector<int> heuristics (hValues, hValues + sizeof(hValues) / sizeof(int)) ;
    AStarSearch(mat, 0, 1, heuristics);
    return 0;
};

By observing the algorithm, we see that the only difference from Dijkstra's algorithm is the addition of the heuristic estimate when choosing the next vertex to explore. In scenarios like map navigation, where heuristic functions are available, the heuristics help guide the search towards the destination while maintaining robustness through exploration. Due to the minimal changes, the time and space complexities remain the same as Dijkstra's algorithm: $O(V^2)$ and $O(V)$, respectively. However, A* search typically requires fewer iterations compared to Dijkstra's algorithm in practice, provided a good heuristic function is available.

Conclusion

In this article, we discussed how search can be improved with Dijkstra's algorithm and A* search by introducing weights and heuristics, which are often present in graph representations of real-world problems. However, the real world is often more complex and, most importantly, non-deterministic. This necessitates more sophisticated ways to model real-world problems as graphs and develop corresponding search algorithms, leading us into the field of reinforcement learning. We will cover more prerequisites before starting the reinforcement learning series, so stay tuned!

Exercises

From this article, there will be an exercise section where you can test your understanding of the material introduced in the article. I highly recommend solving these questions by yourself after reading the main part of the article. You can click on each question to see its answer.

Resources

• Spanning Tree. 2020. How Dijkstra's Algorithm Works. YouTube.