Question 181961 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – how to find shortest path in array to go from station No 2 to station No 6

I have a database where the routes table contains only fromstationid and tostationid.

What I need to find is the shortest path to go from station Number 2 to station Number 6.

Note: I can’t make any changes to database

routes:

let routes = [
  { id:1, fromstationid: 1, tostationid: 2 },
  { id:2, fromstationid: 2, tostationid: 1 },
  { id:3, fromstationid: 2, tostationid: 3 },
  { id:4, fromstationid: 3, tostationid: 2 },
  { id:5, fromstationid: 3, tostationid: 4 },
  { id:6, fromstationid: 4, tostationid: 3 },
  { id:7, fromstationid: 3, tostationid: 6 },
  { id:8, fromstationid: 6, tostationid: 3 },
  { id:9, fromstationid: 4, tostationid: 5 },
  { id:10, fromstationid: 5, tostationid: 4 },
  { id:11, fromstationid: 7, tostationid: 6 },
  { id:12, fromstationid: 6, tostationid: 7 }
]

If I need to go from station 2 to station 6,
the output should be:

[
  { id: 3, fromstationid: 2, tostationid: 3 },
  { id: 7, fromstationid: 3, tostationid: 6 }
]

I try to calculate the path

    let originId = 2
    let destinationId = 6

    let visited = [];
    let inroute = []
    let stationtofind = originId
    
    for (let i = 0; i < routes.length; i++) {
        const st = routes[i];

        let f = routes.find(st2 => (st2.fromstationid === st.tostationid
                                    && st.fromstationid === stationtofind)
                                    && !(st2.tostationid in visited))
        visited.push(st.fromstationid)
        stationtofind = st.tostationid
        if (f) {
            inroute.push(f)
            if (f.tostationid === destinationId) {
                break
            }
        }
    }

    console.log(inroute);

But the output is this:

[
  { id: 1, fromstationid: 1, tostationid: 2 },
  { id: 3, fromstationid: 2, tostationid: 3 },
  { id: 7, fromstationid: 3, tostationid: 6 }
]

When it should have been this:

[
  { id: 3, fromstationid: 2, tostationid: 3 },
  { id: 7, fromstationid: 3, tostationid: 6 }
]
Tags:

2

Answers


  1. 0

    This should solve the problem, using the DFS algorithm you can find the shortest path:

    let routes = [
  { id:1, fromstationid: 1, tostationid: 2 },
  { id:2, fromstationid: 2, tostationid: 1 },
  { id:3, fromstationid: 2, tostationid: 3 },
  { id:4, fromstationid: 3, tostationid: 2 },
  { id:5, fromstationid: 3, tostationid: 4 },
  { id:6, fromstationid: 4, tostationid: 3 },
  { id:7, fromstationid: 3, tostationid: 6 },
  { id:8, fromstationid: 6, tostationid: 3 },
  { id:9, fromstationid: 4, tostationid: 5 },
  { id:10, fromstationid: 5, tostationid: 4 },
  { id:11, fromstationid: 7, tostationid: 6 },
  { id:12, fromstationid: 6, tostationid: 7 }
]

let originId = 2;
let destinationId = 6;

let visited = new Set();
visited.add(originId);
let shortestRoute = [];
DFS(originId, destinationId, [], visited);
console.log(shortestRoute);

function DFS(currStationID, destinationId, inroute, visited){
    
    if(currStationID === destinationId){
        if(shortestRoute.length === 0 || shortestRoute.length > inroute.length){
            shortestRoute = [...inroute];
        }
        return;
    }

    let nextStations = routes.map(st => (st.fromstationid === currStationID && !visited.has(st.tostationid)) ? st : undefined).filter(st => st !== undefined);

    for(let nextStation of nextStations){
        visited.add(nextStation.tostationid);
        DFS(nextStation.tostationid, destinationId, [...inroute, nextStation], visited);
        visited.delete(nextStation.tostationid);
    }
}
    Login or Signup to reply.
  2. 0

    There are at least two issues in your code:

    • The loop always starts at 0, and routes[0], which cannot be right if the starting station is a dynamic input.
    • The algorithm is greedy in the sense that it will content itself with finding any path to the target station — there is no logic that ensures it is the shortest.

    The algorithm that is most convenient for finding a shortest path (in a nonweighted graph) is by performing a breadth-first search (BFS). To efficiently look up which stations have direct routes from a given station, it is good to create an adjacency list for each station.

    Here is an implementation:

    function createGraph(routes) {
     const adj = {};
     for (const route of routes) {
         (adj[route.fromstationid] ??= []).push(route);
         adj[route.tostationid] ??= [];
     }
     return adj;
}

function shortestPath(adj, originId, destinationId) {
    let frontier = [originId]; // list of nodes to be expanded
    const comeFrom = {}; // Key/key pairs representing a linked list 
    while (frontier.length) {
        if (frontier.includes(destinationId)) { // BINGO!
            // Convert linked list to path array
            const path = [];
            let id = destinationId;
            while (id !== originId) {
                path.push(comeFrom[id]);
                id = comeFrom[id].fromstationid;
            }
            return path.reverse();
        }
        // Expand frontier's nodes into a next frontier
        const nextFrontier = [];
        for (const id of frontier) {
            for (const route of adj[id]) {
                if (comeFrom[route.tostationid]) continue;
                comeFrom[route.tostationid] = route;
                nextFrontier.push(route.tostationid);
            }
        }
        frontier = nextFrontier;        
    }
    // If we get here, the destination is not reachable from the origin
}

// Example run
let routes = [
    { id:1, fromstationid: 1, tostationid: 2 },
    { id:2, fromstationid: 2, tostationid: 1 },
    { id:3, fromstationid: 2, tostationid: 3 },
    { id:4, fromstationid: 3, tostationid: 2 },
    { id:5, fromstationid: 3, tostationid: 4 },
    { id:6, fromstationid: 4, tostationid: 3 },
    { id:7, fromstationid: 3, tostationid: 6 },
    { id:8, fromstationid: 6, tostationid: 3 },
    { id:9, fromstationid: 4, tostationid: 5 },
    { id:10, fromstationid: 5, tostationid: 4 },
    { id:11, fromstationid: 7, tostationid: 6 },
    { id:12, fromstationid: 6, tostationid: 7 }
];

const adj = createGraph(routes);
const path = shortestPath(adj, 2, 6);
console.log(path);
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search