Find Minimum Path Between Nodes

Demonstrates how to find and highlight the shortest path between two nodes using pathfinding algorithms.

Find Minimum Path Between Nodes

Functional Overview

This example demonstrates how to find and highlight the shortest path between two nodes in a graph using pathfinding algorithms.

Implementation of Key Features

Pathfinding Algorithm

Implement BFS or Dijkstra’s algorithm for shortest path:

const findMinPath = (startId: string, endId: string): string[] => {
    const visited = new Set<string>();
    const queue: { nodeId: string; path: string[] }[] = [
        { nodeId: startId, path: [startId] }
    ];

    while (queue.length > 0) {
        const { nodeId, path } = queue.shift()!;
        if (nodeId === endId) return path;

        if (visited.has(nodeId)) continue;
        visited.add(nodeId);

        const neighbors = getNeighbors(nodeId);
        for (const neighbor of neighbors) {
            queue.push({ nodeId: neighbor.id, path: [...path, neighbor.id] });
        }
    }
    return [];
};

Highlight Path

Visualize the found path:

const highlightPath = (path: string[]) => {
    const allNodes = graphInstance.getNodes();
    const allLines = graphInstance.getLines();

    allNodes.forEach(node => {
        const isInPath = path.includes(node.id);
        graphInstance.updateNode(node, {
            opacity: isInPath ? 1 : 0.2,
            color: isInPath ? '#43a2f1' : undefined
        });
    });

    allLines.forEach(line => {
        const isInPath = path.includes(line.from) && path.includes(line.to) &&
            isConsecutiveInPath(path, line.from, line.to);
        graphInstance.updateLine(line, {
            color: isInPath ? '#43a2f1' : '#cccccc',
            lineWidth: isInPath ? 3 : 1
        });
    });
};

Path Selection

Allow users to select start and end nodes:

let selectedNodes: string[] = [];

const onNodeClick = (node: RGNode) => {
    selectedNodes.push(node.id);
    if (selectedNodes.length === 2) {
        const path = findMinPath(selectedNodes[0], selectedNodes[1]);
        highlightPath(path);
        selectedNodes = [];
    }
};

Creative Use Cases

• Network Analysis: Find optimal routes in networks
• Social Networks: Shortest connection between people
• Transportation: Route planning and optimization
• Supply Chain: Optimize logistics paths
• Game Development: Pathfinding for AI characters