Как найти кратчайший путь между точками с учетом дорог?

Question

Есть игровая карта, созданная с помощью Leafletjs. На карте имеются точки, к которым привязаны готовые пути. У точки может быть несколько путей, если она стоит на перекрестке. Путь - это линия, состоящая из небольших отрезков. Условно:

//точки
const waypoints = [
    [
        'id': 'point1',
        'ways': ['way1', 'way2'] //точка стоит на перекрестке
    ],
    [
        'id': 'point2',
        'ways': ['way7'] //точка стоит на простом пути
    ],
    [
        'id': 'point3',
        'ways': [...]
    ],
    //...
]

//пути
const ways = [
    ['id': 'way1'],
    ['id': 'way2'],
    //...
]

Каким образом можно найти все точки, через которые нужно пройти от point1 до point2 по готовым путям? Мой недокод:

const waypointFrom = waypoints[5]
const waypointTo = waypoints[66]

const result = [], ways2 = []
function isTrue(waypoint)
{
    for (const way of waypoint.ways) {
        if (ways2.indexOf(way.id) !== -1) continue
        ways2.push(way.id)
        
        if (waypointTo.ways.indexOf(way.id) !== -1) return true
        
        for (const waypoint2 of waypoints) {
            if (waypoint2.id === waypointFrom.id || waypoint2.id === waypointTo.id) continue
            
            for (const way2 of waypoint2.ways) {
                if (way2.id === way.id && isTrue(waypoint2)) {
                    result.push(waypoint2)
                    return true
                }
            }
        }
    }
    
    return false
}

Маршрут он конечно находит, но только первый попавшийся и длинный.

Красным цветом нарисован результат, а серым пунктиром собственно сами пути

Answer 1

Нагуглил "Алгоритм Дейкстры" и нашел пример с готовым кодом, которым и воспользовался.

class Graph
{
    constructor() {
        this.nodes = [];
        this.adjacencyList = {};
    }

    addNode(node) {
        this.nodes.push(node);
        this.adjacencyList[node] = [];
    }

    addEdge(node1, node2, weight) {
        this.adjacencyList[node1].push({node:node2, weight: weight});
        this.adjacencyList[node2].push({node:node1, weight: weight});
    }

    findPathWithDijkstra(startNode, endNode) {
        let times = {};
        let backtrace = {};
        let pq = new PriorityQueue();

        times[startNode] = 0;

        this.nodes.forEach(node => {
            if (node !== startNode) {
                times[node] = Infinity
            }
        });

        pq.enqueue([startNode, 0]);

        while (!pq.isEmpty()) {
            let shortestStep = pq.dequeue();
            let currentNode = shortestStep[0];
            this.adjacencyList[currentNode].forEach(neighbor => {
                let time = times[currentNode] + neighbor.weight;

                if (time < times[neighbor.node]) {
                    times[neighbor.node] = time;
                    backtrace[neighbor.node] = currentNode;
                    pq.enqueue([neighbor.node, time]);
                }
            });
        }

        let path = [endNode];
        let lastStep = endNode;
        while(lastStep !== startNode) {
            path.unshift(backtrace[lastStep])
            lastStep = backtrace[lastStep]
        }
        console.log(`Path is ${path} and time is ${times[endNode]}`)
        return path
    }
}

class PriorityQueue {
    constructor() {
        this.collection = [];
    }

    enqueue(element){
        if (this.isEmpty()){
            this.collection.push(element);
        } else {
            let added = false;
            for (let i = 1; i <= this.collection.length; i++){
                if (element[1] < this.collection[i-1][1]){
                    this.collection.splice(i-1, 0, element);
                    added = true;
                    break;
                }
            }
            if (!added){
                this.collection.push(element);
            }
        }
    };

    dequeue() {
        let value = this.collection.shift();
        return value;
    };
    isEmpty() {
        return (this.collection.length === 0)
    };
}

Затем зарегистрировал все точки, а также точки находящиеся на 1 пути. В итоге получилось что-то вроде:

Ссылка на оригинал кода

БЛОГ НА HUSL

Как найти кратчайший путь между точками с учетом дорог?

Ответы (1 шт):