Short version of question:
Can I use Dijkstra's algorithm to find the shortest path in non-planar graph?
Long version:
I'm working on an project in which I'm gonna find shortest path in a multi-storey building. In order to do that, I was about to create a graph in my application and use Dijkstra's algorithm. However, my tutor told me:Dijkstra's algorithm needs a planar graph, while you are going to have three-dimensional graph (?), as you need to implement the fact the building is a multi-storey one.
Is there something like "three dimensional graph"? I solved that problem by creating a subgraph for each storey (each marked with different colour) and then by connecting them into one graph, but now my graph is not planar.
However, I didn't find nothing on the Internet, what would tell me "yes, you need a planar graph" or "no, you don't need a planar graph".
I tried solving the shortest path manually and it seems fine, as the edges of my graph are not gonna have value <0.
Anyway, I hope some of you have some information, I could share to my tutor to explain the issue "Can I use Dijkstra's algorithm here or not?".
Best Answer
Planarity is not a requirement. Any graph will do, as long as the lengths of the edges is positive. See wiki page as well.