Djikstra Algorithm to avoid or not to avoid an obstacle vertex

48 Views Asked by At

Okay, first forgive my english, second I want to ask you this question that comes into my mind all of sudden and trying to figure it out which I find hard to do it,

Im quite understand how Djikstra works, and I know how to make a program with C++ of that Djikstra, the thing is, I want to add an obstacle, which is a vertex, that this vertex may be qualified as below :

  1. this vertex is one of vertices of shortest path to a final vertex that Djikstra will choose of course in his step,
  2. BUT, this vertex in this case must be avoid for some reason such as a traffic jam, which is not pretty hard, just tell Djikstra to not to choose the vertex which I programmed like : deleting the vertex from my graph, so Djikstra will aim for another shortest path of course,
  3. in case finding another shortest path, I find that my program wont update the path to the final vertex, which I realize that the "obstacle vertex" must be included to the path, because there's no way to the final vertex without taking the "obstacle vertex",
  4. I try to make a conditional statement on it, if the path wont updated then, do not delete the vertex from the graph,
  5. I got the final result,

But, I dont know how to solve this program into a bigger case, for like 5-6 obstacle vertex, lets say, I delete all the 6 vertex, and end up with no result, which vertex should I redelete?