5.31. Path-finding algorithm

发布时间 ： 2025-10-25 13:35:42 UTC      

Page Views: 17 views

The pathfinding algorithm of a graph can also be realized by depth-first traversing the dfs to find the path of the graph graph from the starting s point to other points. In the implementation class of the previous section, add global variables from array to record the path, from [i] Represents the last node of I on the path to be looked up.

First, construct a function to initialize the initial condition of the pathfinding algorithm, from = new int [G.V()] And from = new int [G.V()] And set the default value in the loop, the visited array is all false,from, the array is all-1, and then the starting node is recursively processed by dfs.

...
// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
public Path(Graph graph, int s){
    // 算法初始化
    G = graph;
    assert s >= 0 && s < G.V();
    visited = new boolean[G.V()];
    from = new int[G.V()];
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        from[i] = -1;
    }
    this.s = s;
    // 寻路算法
    dfs(s);
}
...

Then to determine whether there is a path from point s to point w, just query the corresponding array values of visited.

...
boolean hasPath(int w){
    assert w >= 0 && w < G.V();
    return visited[w];
}
...

To get the specific path from s point to w point, we use the path method to realize it. We can first judge whether it is connected or not. We can call the hasPath method. From the constructor, we can know that all the paths can be found only by tracing up through the from array.

...
Vector path(int w){
    assert hasPath(w) ;
    Stack s = new Stack();
    // 通过from数组逆向查找到从s到w的路径, 存放到栈中
    int p = w;
    while( p != -1 ){
        s.push(p);
        p = from[p];
    }
    // 从栈中依次取出元素, 获得顺序的从s到w的路径
    Vector res = new Vector();
    while( !s.empty() )
        res.add( s.pop() );
    return res;
}
...
   
 
  5.31.1.  Java instance code  
 
  源码包下载：   Download  
 
 
 Src/runoob/graph/Path.java file code:  
 
 
 
package runoob.graph;
import runoob.graph.read.Graph;
import java.util.Stack;
import java.util.Vector;
/*\*
 \* 寻路
 */
public class Path {
    // 图的引用
    private Graph G;
    // 起始点
    private int s;
    // 记录dfs的过程中节点是否被访问
    private boolean[] visited;
    // 记录路径, from[i]表示查找的路径上i的上一个节点
    private int[] from;
    // 图的深度优先遍历
    private void dfs( int v ){
        visited[v] = true;
        for( int i : G.adj(v) )
            if( !visited[i] ){
                from[i] = v;
                dfs(i);
            }
    }
    // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
    public Path(Graph graph, int s){
        // 算法初始化
        G = graph;
        assert s >= 0 && s < G.V();
        visited = new boolean[G.V()];
        from = new int[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
        }
        this.s = s;
        // 寻路算法
        dfs(s);
    }
    // 查询从s点到w点是否有路径
    boolean hasPath(int w){
        assert w >= 0 && w < G.V();
        return visited[w];
    }
    // 查询从s点到w点的路径, 存放在vec中
    Vector path(int w){
        assert hasPath(w) ;
        Stack s = new Stack();
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }
        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        Vector res = new Vector();
        while( !s.empty() )
            res.add( s.pop() );
        return res;
    }
    // 打印出从s点到w点的路径
    void showPath(int w){
        assert hasPath(w) ;
        Vector vec = path(w);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )
                System.out.println();
            else
                System.out.print(" -> ");
        }
    }
}
      
                    
                
                

                    

                        

                            
                                文章链接
                            
                            ：
                            5.31. Path-finding algorithm 
                        

                    

                

            
        
        

            

    
        

            

                

                    
                        
                        
                            
Principles and Applications of WebGIS 

                        
                        
                             37
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
Web框架 

                        
                        
                             942
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
WEB基础 

                        
                        
                             287
                        
                    
                    
                        

                            
 
 
 

                        

                    
                

                
            

        

    

    
        

            

                

                    
                        
                        
                            
Principles, Technologies, and Methods of Geographic Information Systems 

                        
                        
                             102
                        
                    
                    
                        

                            
 
 
 In recent years, Geographic Information Systems (GIS) have undergone rapid development in both theoretical and practical dimensions. GIS has been widely applied for modeling and decision-making support across various fields such as urban management, regional planning, and environmental remediation, establishing geographic information as a vital component of the information era. The introduction of the “Digital Earth” concept has further accelerated the advancement of GIS, which serves as its technical foundation. Concurrently, scholars have been dedicated to theoretical research in areas like spatial cognition, spatial data uncertainty, and the formalization of spatial relationships. This reflects the dual nature of GIS as both an applied technology and an academic discipline, with the two aspects forming a mutually reinforcing cycle of progress.