When extracting path from start to destination node ,iterate through vector in descending order using the returned vector then it is possible to find path in O(n)-Time while otherwise in O(n**2)!
So:
let mut node: &Node = dest;
for i in vec.len() to 0 /* from top to bottom */ {
if searchedVector = node {
node = searchedVector.prev;
// One node of path found!
}
}
Same procedure is also possible in ascending order using start node. This exploits the fact that the dijkstra algorithm proceeds level by level, i.e. the nodes of a path always appear in the vector in the order in which they were viewed.
When extracting path from start to destination node ,iterate through vector in descending order using the returned vector then it is possible to find path in O(n)-Time while otherwise in O(n**2)!
So:
let mut node: &Node = dest;
for i in vec.len() to 0 /* from top to bottom */ {
if searchedVector = node {
node = searchedVector.prev;
// One node of path found!
}
}
Same procedure is also possible in ascending order using start node. This exploits the fact that the dijkstra algorithm proceeds level by level, i.e. the nodes of a path always appear in the vector in the order in which they were viewed.