Encountering an issue while implementing Dijkstra's algorithm on a multigraph. The graph consists of nodes representing stops with information and connections to other stops (edges). However, the challenge arises when there are multiple bus options between two nodes.
For example: Traveling from stop A to stop B can be done using bus 1, bus 2, bus 3, etc.
This results in finding a path that may not be optimal due to choosing an incorrect bus.
Another complication is having stops with the same name, but different directions.
The representation of my graph is as follows:
{
...,
"5382778889": {
"name": "Heroes Square",
"coordinates": {
"latitude": -25.9351311,
"longitude": 32.5792925
},
"street": "Acordos de Lusaka Avenue",
"connections": [
{
"stop": 6797387579,
"bus": 10046632,
"path": [...]
},
...
],
"walking_connections": [
{
"stop": "5382778890"
}
]
},
...
}
The implementation of my Dijkstra's algorithm is shown below:
findPaths(stops, startPoint, endPoint) {
const distance = {};
const queue = new PriorityQueue();
const previous = {};
const buses = {};
const visited = new Set();
for (const stop in stops) {
distance[stop] = stop == startPoint ? 0 : Infinity;
queue.enqueue(stop, distance[stop]);
};
while (!queue.isEmpty()) {
const currentStop = Number(queue.dequeue());
if (visited.has(currentStop)) {
continue;
};
visited.add(currentStop);
if (currentStop == endPoint) {
const shortestPath = [];
let stop = {
stop: endPoint,
name: stops[endPoint].name,
coordinates: stops[endPoint].coordinates,
street: stops[endPoint].street,
path: [],
bus: null,
};
...
return shortestPath;
};
if (stops[currentStop] && stops[currentStop].connections) {
...
};
};
if (stops[currentStop].walking_connections) {
...
};
};
...
};