Discovering the most efficient route among a collection of objects in JavaScript

Question

Discovering the most efficient route among a collection of objects in JavaScript

Presented here is an array of objects:

const data = [
    { start: "X", end: "Y", distance: 5},
    { start: "X", end: "Z", distance: 4},
    { start: "Z", end: "Y", distance: 8},
    { start: "Y", end: "V", distance: 9},
    { start: "V", end: "Z", distance: 17},
]

The task at hand is to determine the shortest path based on 'distance' from point X to Y. To achieve this, a 2D distance matrix has been created.

findUniquePoints() {

        let _points = []
        data.forEach(item => {
            if (!_points.includes(item.start)) {
                _points.push(item.start)
            }
            if (!_points.includes(item.end)) {
                _points.push(item.end)
            }

        })
        return _points
    }

    this.pointsArray = this.findUniquePoints()
    let _matrix = []
    this.pointsArray.forEach((point, index) => {
        _matrix[index] = this.pointsArray.map(() => 0)
   })

   data.forEach(item => {
       _matrix[this.pointsArray.indexOf(item.start)][this.pointsArray.indexOf(item.end)] = item.distance
   })
   console.log(_matrix)
  // The log displays the populated matrix:
  //[[0, 5, 4, 0][0, 0, 0, 9][0, 8, 0, 0][0, 0, 17, 0]]

javascript arrays data-structures

Answer 1

Answer №1

Implementing a variation of the Dijkstra pathfinding algorithm, construct a map detailing the steps to reach each destination while keeping a record of the path taken:

var obstacles = [
    { start: "A", end: "C", distance: 5 },
    { start: "A", end: "D", distance: 4 },
    { start: "D", end: "C", distance: 8 },
    { start: "C", end: "B", distance: 9 },
    { start: "B", end: "D", distance: 17 },
];
function findOptimalPath(start, end) {
    var openList = obstacles
        .filter(function (item) {
            return item.start == start || item.end == start;
        });
    var resultMap = {};
    resultMap[start] = { distance: 0, route: start };
    obstacles
        .filter(function (item) {
            return item.start == start || item.end == start;
        })
        .forEach(function (value, index) {
            if (resultMap[value.end] === void 0) {
                resultMap[value.end] = { distance: value.distance, route: start + value.end };
            }
            else if (resultMap[value.end].distance > value.distance) {
                resultMap[value.end] = { distance: value.distance, route: start + value.end };
            }
        });
    while (resultMap[end] === void 0) {
        for (var node in resultMap) {
            if (resultMap.hasOwnProperty(node)) {
                var currentNode = resultMap[node];
                obstacles
                    .filter(function (item) {
                        return item.start == node || item.end == node || item.start == node || item.end == node;
                    })
                    .forEach(function (value, index) {
                        var totalDistance = value.distance + currentNode.distance;
                        if (resultMap[value.end] === void 0) {
                            resultMap[value.end] = { distance: totalDistance, route: currentNode.route + value.end };
                        }
                        else if (resultMap[value.end].distance > totalDistance) {
                            resultMap[value.end] = { distance: totalDistance, route: currentNode.route + value.end };
                        }
                        if (resultMap[value.start] === void 0) {
                            resultMap[value.start] = { distance: totalDistance, route: currentNode.route + value.end };
                        }
                        else if (resultMap[value.start].distance > totalDistance) {
                            resultMap[value.start] = { distance: totalDistance, route: currentNode.route + value.end };
                        }
                    });
            }
        }
    }
    return resultMap[end];
}
//TEST
var bestRoute = findOptimalPath("A", "B");
console.log(bestRoute);

Answer 2

Implementing a variation of the Dijkstra pathfinding algorithm, construct a map detailing the steps to reach each destination while keeping a record of the path taken:

var obstacles = [
    { start: "A", end: "C", distance: 5 },
    { start: "A", end: "D", distance: 4 },
    { start: "D", end: "C", distance: 8 },
    { start: "C", end: "B", distance: 9 },
    { start: "B", end: "D", distance: 17 },
];
function findOptimalPath(start, end) {
    var openList = obstacles
        .filter(function (item) {
            return item.start == start || item.end == start;
        });
    var resultMap = {};
    resultMap[start] = { distance: 0, route: start };
    obstacles
        .filter(function (item) {
            return item.start == start || item.end == start;
        })
        .forEach(function (value, index) {
            if (resultMap[value.end] === void 0) {
                resultMap[value.end] = { distance: value.distance, route: start + value.end };
            }
            else if (resultMap[value.end].distance > value.distance) {
                resultMap[value.end] = { distance: value.distance, route: start + value.end };
            }
        });
    while (resultMap[end] === void 0) {
        for (var node in resultMap) {
            if (resultMap.hasOwnProperty(node)) {
                var currentNode = resultMap[node];
                obstacles
                    .filter(function (item) {
                        return item.start == node || item.end == node || item.start == node || item.end == node;
                    })
                    .forEach(function (value, index) {
                        var totalDistance = value.distance + currentNode.distance;
                        if (resultMap[value.end] === void 0) {
                            resultMap[value.end] = { distance: totalDistance, route: currentNode.route + value.end };
                        }
                        else if (resultMap[value.end].distance > totalDistance) {
                            resultMap[value.end] = { distance: totalDistance, route: currentNode.route + value.end };
                        }
                        if (resultMap[value.start] === void 0) {
                            resultMap[value.start] = { distance: totalDistance, route: currentNode.route + value.end };
                        }
                        else if (resultMap[value.start].distance > totalDistance) {
                            resultMap[value.start] = { distance: totalDistance, route: currentNode.route + value.end };
                        }
                    });
            }
        }
    }
    return resultMap[end];
}
//TEST
var bestRoute = findOptimalPath("A", "B");
console.log(bestRoute);

Discovering the most efficient route among a collection of objects in JavaScript

Answer №1

Similar questions

Ways to transfer a value from a JavaScript file to a PHP file?

Obtaining the following class name from elements

The current situation is not effective; it is causing an error saying "Uncaught TypeError: Cannot read property 'substring' of undefined"

What is the method for converting a canvas to a jpg file in Ionic?

Exploring Angular2 components featuring setInterval or setTimeout functions

Bring in camera from gltf

Why is my Angular router displaying the page twice in the browser window?

Is there a way to replace null values with empty strings when using json_encode?

The rotation duplication feature in THREE.js is malfunctioning

I'm having trouble with my controller - not sure what the problem is

Attempting to loop through a list and create a retrieval function for each item

What is the best way to verify the information submitted in a form within a Bootstrap modal window

What is the best method for transferring an audio file from an Express (Node.js) server to a Flask server

Utilizing retrieved data from API calls in subsequent Vue 3 methods

Voiceover on IOS fails to properly read the content inside a div element

casperjs is encountering difficulty locating the id even after setting it

Transferring information from JavaScript to Node.js

Retrieve specific information using the identifier from the URL parameters during server-side rendering

Is the token in localStorage valid? Here's how to find out!

Utilizing Multiple MongoDB Connections in a Node.js Application