Content#

• Finding the shortest path between two nodes in a graph
• Dijkstra’s algorithm
• The A* (“A-star”) algorithm
• Priority Queues
• Problems we can solve using path-finding algorithms

What is graph#

• Nodes(vertices)
• Edges(arcs)
• Directed or undirected graph

Path finding#

• Suppose that I want to get from one subway station to another by the quickest route.
• Suppose that I want to get from one country to another country by the cheapest way.

What should we do for these two questions?

• The solution for finding the quickest route is:
  1. Represent the subway as a graph, with stations as nodes.
  2. Label each edge of the graph with its “cost”-the time it would take to traverse that edge.
  3. The time taken to traverse any path is then the sum of the costs of the edges you move through.
  4. So all we have to do is find the path with the shortest total cost.

• How to implement the solution we mentioned above?
  • Dijkstra’s algorithm
  • The A* (“A-star”) algorithm

Dijkstra’s algorithm#

• Calculates shortest path between two nodes, which we shall call Start and End.
• Assumes that there are no negative edge costs.
• Works on both directed and undirected graphs.

• If nodes represent subway stations, the cost could represent

A. the line length between stations.
B. the fee we spend from one station to another
C. the time we spend from one station to another
D. all of above

Summary:
Cost could be any meaningful thing to edges

• Makes use of two sets of nodes:
  • Closed - If a node N is in this set then we have already calculated the shortest path from Start to N.
  • Open - If a node N is in this set then we may have considered a path from Start to N but we don’t yet know whether it is the shortest path.

• For each node we maintain two extra pieces of information:
  • The g-value of a node. ----This is the total cost of the best path that we have found (so far) from Start to this node.
  • A “back” pointer to the previous node on that path.
• The Open set behaves as a priority queue, in which the node with the lowest g-value has the highest priority.

What is the feature of the PQ?

• Dijkstra’s algorithm only works on undirected graph, yes or no?
• The node with the lowest g-value has the highest priority, yes or no?
• Dijkstra’s algorithm is used for?

• Are there negative edge costs for Dijkstra’s algorithm?
• Does the Closed Set contain all of the calculated nodes?
• Does the Closed Set contain the visited nodes?
• What does the edge‘s cost represent?

1
set Closed to be empty
2
add all nodes in the graph to Open.
3
set the g-value of Start to 0, and the g-value of all the other nodes to ∞
4
set previous to be none for all nodes.
5
while End is not in Closed do
6
    let X be the node in Open that has the lowest g-value (highest priority)
7
    remove X from Open and add it to Closed.
8
    if X is not equal to End then
9
        for each node N that is adjacent to X in the graph, and also in Open do
10
            let g’ = g-value of X + cost of edge from X to N
11
            if g’ is less than the current g-value of N then
12
                change the g-value of N to g’
13
                make N’s previous pointer point to X
14
            endif
15
        endfor
16
    endif
17
endwhile

reconstruct the shortest path from Start to End by following “previous” pointers to find the previous node to End, the previous node to that previous node, and so on.

Dijkstra’s algorithm#

• Are there negative edge costs for Dijkstra’s algorithm?
  • No. Dijkstra’s algorithm only works with non-negative edge costs/weights. It cannot process negative edge costs, as its greedy selection of the shortest path node fails when negative edges exist (a later path could become shorter, but the algorithm never revisits finalized nodes).
• The node with the lowest g-value has the highest priority, yes or no?
  • Yes. Dijkstra’s uses a min-priority queue that always prioritizes and expands the unvisited node with the smallest current g-value (the known shortest path cost from the start node).
• What does the edge‘s cost represent?
  • An edge’s cost is a quantitative weight that represents the expense to traverse between two connected nodes. It can stand for physical distance, travel time, fuel cost, energy consumption, network latency, number of steps, or any measurable effort/loss between two vertices in a graph.

• Thinking question:
  • The disadvantages of Dijkstra’s algorithm?
    1. Cannot handle negative edge weights
       It relies on a greedy strategy: once a node is marked as visited/finalized, its shortest path is never updated again. Negative edge weights can create shorter alternative paths to already finalized nodes, making the algorithm give incorrect results. It also cannot detect negative cycles.
    2. Only single-source shortest path
       It only calculates the shortest path from one starting node to all other nodes. To get all-pairs shortest paths, you must run the algorithm repeatedly for every vertex, which is inefficient.
    3. Inefficient for large sparse graphs (naive implementation)
       The basic adjacency-matrix version runs in $O(V^2)$ time, which is slow for graphs with many vertices. Even with a binary priority queue, it is $O(E \log V)$, which is less optimal for very large-scale graphs compared to other specialized algorithms.
    4. Greedy limitation
       It makes locally optimal choices at each step, which do not always lead to the global optimum if graph conditions change (only works reliably with fixed, non-negative edge costs).
    5. Not suitable for dynamic graphs
       It cannot easily adapt to graphs where edge weights change dynamically; it requires re-running the whole algorithm from scratch.

Are we nearly there yet?
Heuristically informed search#

• Suppose that the graph for Exercise 1 had been drawn to scale, and that we knew the co-ordinates of each point. For example G might be at (0,0), A at (20,0), D at (0,3), and so on.
• This means that we can calculate the straight line distance between any two points using Pythagoras’ theorem（毕达哥拉斯定理，勾股定理）
• We know that the length of the shortest path between two points must be greater than or equal to the length of the straight line that connects them. We can therefore use the straight line distance as a heuristic, that is to say a rough and ready measure of how long a path between two points is likely to be.
• Using our heuristic, we can see that this wasn’t so smart! Although we can get from A to B at a cost of only 10 units, it is going to cost us at least another 31.1 units to get all the way from B to E. It might be more sensible to look at paths leading off from G.
• When we used Dijkstra’s algorithm to find the shortest path, we calculated g‑values for G and B, and then added B to the closed set, because its g‑value was the lower. After that we calculated a g‑value for C.
• Using our heuristic, we can see that this wasn’t so smart! Although we can get from A to B at a cost of only 10 units, it is going to cost us at least another 31.1 units to get all the way from B to E. It might be more sensible to look at paths leading off from G.

The A* algorithm#

• The A* (“A-star”) algorithm makes use of an admissible heuristic to aid the search for a path between two points. It was invented in 1968 at Stanford International for use in Shakey the robot.
• The heuristic doesn’t have to be the straight-line distance, but it does have to be admissible.
• Also we can’t have negative edge.
• For each node we calculate an f-value which is equal to the g-value plus the heuristic value for that node.
• There are different variants of the A* algorithm, and different ways of describing each variant. Since we have already met Dijkstra’s algorithm, we shall present A* as a modification of Dijkstra.
• The Open set still behaves as a priority queue, but priority is determined using f-values rather than g-values.
• In other words when we choose a node to add to the Closed set, we pick the one with the lowest f-value, rather than the lowest g-value.

1
set Closed to be empty
2
add all nodes in the graph to Open.
3
set the g-value of Start to 0, and the g-value of all the other nodes to ∞
4
set previous to be none for all nodes.
5
    while End is not in Closed do
6
    let X be the node in Open  that has the lowest f-value (highest priority)
7
    (f-value is g-value + the heuristic value for that node)
8
    remove X from Open and add it to Closed.
9
    if X is not equal to End then
10
    for each node N that is adjacent to X in the graph, and also in Open do
11
      let g’  = g-value of X + cost of edge from X to N
12
      if g’ is less than the current g-value of N then
13
        change the g-value of N to g’
14
        make its previous pointer point to X
15
      endif
16
    endfor
17
  endif
18
endwhile

A* algorithm#

• The meaning of H-value?
  • The H-value (heuristic value) is the estimated approximate cost from the current node to the target/goal node in the graph.
  • It is a guess (not the real exact path cost) used by A* to guide the search toward the goal efficiently.
• Could we set H-value for each node randomly?
  • No, we cannot.
    • A* algorithm depends on a reasonable heuristic function. Random H-values provide no meaningful guidance toward the goal.
    • Random H may overestimate the real path cost, breaking the admissible heuristic rule. This makes A* lose optimality (may not find the shortest path).
    • Random H also causes inefficient, aimless searching and greatly increases computation time.

A note on Priority queues#

• In both Dijkstra’s and the A* algorithm, we represent the Open set as a min-priority queue. The priority of a node is determined by its g-value (Dijkstra) or f-value (A*).
• The use of priority queues makes the algorithms more efficient because removing a node becomes O(log n) rather than O(n).
• However the priority queue must be implemented in such a way that the priority of a node can be altered after it has been added to the queue.
• Note that the PriorityQueue class in the Java API does not allow this (you can alter the priority of the node after adding it, but the queue will not then behave correctly).

Other problems that we can tackle using pathfinding algorithms#

• Consider the familiar puzzle where a set of 8 tiles are arranged in a grid with one empty square, and where the tiles must be put into order by repeatedly sliding tiles into the empty square.
• We can represent this problem as a graph, where the nodes are the different possible arrangements of the tiles within the grid. There is an edge between two nodes, with a cost of 1, if we can get from the first node to the second by sliding a tile into the empty square.
• We could solve the problem of putting an arrangement of tiles into the correct order by finding the shortest path through the graph that ends with the tiles in the right order. We could use Dijkstra to do this. We could use A*. A possible heuristic would be the number of tiles that are in the “wrong” place.

Summary#

• Both Dijkstra’s and the A* algorithm solve the problem of finding the shortest path between two nodes in a graph.
• Both algorithms use an Open set of nodes. The variant of A* presented in this lecture also uses a Closed set.
• The Open set behaves as a priority queue, with priority determined by the g-values of nodes (Dijkstra) or their f-values (A*).
• The A* algorithm makes use of an admissible heuristic to guide the search for the shortest path.
• Path-finding algorithms such as Dijkstra and A* can be used to find routes on maps. They can also be used to solve other problems that can be represented as graphs.