Discuss route planning analysis of pathfinding algorithm and code implementation

The pathfinding algorithm is one of the commonly used algorithms in the fields of computer graphics and artificial intelligence. It is used to calculate the shortest path or optimal path from one point to another. . In this article, I will introduce in detail two commonly used pathfinding algorithms: Dijkstra's algorithm and A* algorithm

Dijkstra's algorithm

Dijkstra's algorithm It is a breadth-first search algorithm used to find the shortest path between two points in a graph. It works as follows:

We need to create a set S to store the vertices that have found the shortest path

We need to create a set Q , used to store vertices that have not yet found the shortest path

When initializing the distance array dist, you need to set the distance from the starting point to other points to infinity, and the distance from the starting point to itself is Set to 0

Repeat the following steps until the set Q is empty:

• Find the closest distance to the starting point in the set Q vertex u and add it to the set S.
• For each neighbor vertex v of vertex u, update the distance dist[v] from the starting point to v, if dist[v] > dist[u] edge(u, v) , then update dist[v] to dist[u] edge(u, v).

Finally, the dist array stores the shortest path from the starting point to each vertex

The following is written in C# Source code of Dijkstra's algorithm:

class DijkstraAlgorithm
{
    private int[,] graph;
    private int size;

    public DijkstraAlgorithm(int[,] graph)
    {
        this.graph = graph;
        this.size = graph.GetLength(0);
    }

    public int[] FindShortestPath(int start, int end)
    {
        int[] dist = new int[size];
        bool[] visited = new bool[size];

        for (int i = 0; i <h4 id="span-A-algorithm-span"><span>A algorithm</span></h4><p>##A algorithm is a heuristic search algorithm used to find two points in the graph the shortest path between them. The idea of ​​the algorithm is as follows: <span></span></p><p>Create a priority queue openSet to store the vertices to be explored<span></span></p><p>We need to create an array named gScore, using To store the actual cost from the starting point to each vertex<span></span></p><p>We need to create an array named fScore to store the estimated cost from the starting point to the target point<span> </span></p><p>Add the starting point to openSet, set gScore[start] to 0, and set fScore[start] to the estimated cost from the starting point to the target point<span></span></p><p>Repeat the following steps until openSet is empty: <span></span></p>

• Find the vertex current with the smallest fScore in openSet.
• If current is equal to the target point, it means that the shortest path has been found and the path is returned.
• Remove current from openSet.
• For each neighbor vertex neighbor of current, calculate the actual cost tempGScore from the starting point to the neighbor. If tempGScore is less than gScore[neighbor], update gScore[neighbor] to tempGScore, and calculate fScore[neighbor] = gScore[neighbor] estimated cost. If neighbor is not in openSet, add it to openSet.

If openSet is empty, it means that the target point cannot be reached and a null value is returned

The following is A* written in Java Source code of the algorithm:

import java.util.*;class AStarAlgorithm {private int[][] graph;private int size;public AStarAlgorithm(int[][] graph) {this.graph = graph;this.size = graph.length;}public List<integer> findShortestPath(int start, int end) {PriorityQueue<node> openSet = new PriorityQueue();int[] gScore = new int[size];int[] fScore = new int[size];int[] cameFrom = new int[size];boolean[] visited = new boolean[size];Arrays.fill(gScore, Integer.MAX_VALUE);Arrays.fill(fScore, Integer.MAX_VALUE);Arrays.fill(cameFrom, -1);gScore[start] = 0;fScore[start] = heuristicCostEstimate(start, end);openSet.offer(new Node(start, fScore[start]));while (!openSet.isEmpty()) {int current = openSet.poll().index;if (current == end) {return reconstructPath(cameFrom, current);}visited[current] = true;for (int neighbor = 0; neighbor  reconstructPath(int[] cameFrom, int current) {List<integer> path = new ArrayList();path.add(current);while (cameFrom[current] != -1) {current = cameFrom[current];path.add(0, current);}return path;}private class Node implements Comparable<node> {public int index;public int fScore;public Node(int index, int fScore) {this.index = index;this.fScore = fScore;}@Overridepublic int compareTo(Node other) {return Integer.compare(this.fScore, other.fScore);}@Overridepublic boolean equals(Object obj) {if (this == obj) {return true;}if (obj == null || getClass() != obj.getClass()) {return false;}Node other = (Node) obj;return index == other.index;}@Overridepublic int hashCode() {return Objects.hash(index);}}}</node></integer></node></integer>

The above is a detailed introduction to the Dijkstra algorithm and the A* algorithm, including the algorithm idea, process and source code implemented in C# or Java. These two algorithms are commonly used pathfinding algorithms and can be selected and used according to specific needs. Of course, in today’s cities, navigation software can plan things for us.

The above is the detailed content of Discuss route planning analysis of pathfinding algorithm and code implementation. For more information, please follow other related articles on the PHP Chinese website!