🔹.findShortestPath()

data structure ⟩ graph ⟩ .findShortestPath()

• find a shortest path between two nodes using breadth-first search.

• null if not found.

💾 程式

• replit > Graph (js)

// ⭐ Graph
class Graph {

    // omitted ...

    // 🔹 .findShortestPath()
    // - use breadth-first search
    findShortestPath(start, target, { debug = false }={}) {
        
        const queue = new Queue();        // (queue) nodes to visit
        const path = Object.create(null); // (dict) save paths to nodes (self included)
        
        // put `start` node into queue
        queue.enqueue(start);
        path[start] = [start];            // save path to `start`
        
        // while queue is not empty
        while (!queue.isEmpty) {

            // debug (omitted ...)
            
            // pick first node (front) from queue
            const front = queue.dequeue();
            
            // if target is found, return path.
            if (front === target) return path[front];
            
            // else add unexplored neighbors to queue
            const unexplored = this
                .neighborsOf(front)
                .filter(node => !queue.isExplored(node));
            
            for (let child of unexplored) {
                queue.enqueue(child);
                path[child] = path[front].concat(child);    // save path to child
            }
        }

        // queue is empty, no possible path.
        return null;
    }
}

💈範例

graph.findShortestPath('G', 'C')  // [ 'G', 'F', 'M', 'P', 'A', 'C' ]