Search code examples
c#asp.netshortest-path

C# Graph Algorithm for shortest path

Here is my problem. I have a series of photos of different parts of a building and I need to link them together. After that I need to show each photo in sequence to display a path from point A to point B… I.e., from a classroom to a fire escape.

I have done a bit of research and I believe a non-directed unweighted graph should do the trick.

As I have not much experience in this area. I was wondering how I need to store the photos in a data structure and if there are any libraries out there to do the job?

Solution

  • Yes, you need to apply some algorith, that can solve the problem for you.

    You can use this great libray:

    to solve this part of the problem.

    As to the way of storing your data, you need to define vertices (the photos) and edges between vertices like (photo A-photoB), (photo A-photo C), and so on.

    You have to recover that info from the database and load the corresponding structure in quickgraph and let it find the path for you.

    Here you have extensive docs and samples:

    For something similar to this I used:

    • MyEdges class, which implements IEdge<T> (T should be you photo ID type, int or whatever is) - represents the edge between to photos (places)
    • Graph class, which inherits AdjacencyGraph<T,MyRelation>. You load it with the available MyEdges (this is directed graph)
    • PathFinder algorithm class: I inherited from FloydWarshallAllShortestPathAlgorithm<T, MyRelation>

    Then you have to:

    • Create the edges (i.e. read them from the DB)
    • Instance a Graph class, and add all edges to it
    • Use the PathFinder constructor, using the graph as parameter. This finds the paths.

    This algorithm lets you specify to which photos you can go from a given photo (edges), supposes that the distance is similar between them, but you have to define all the routes (from A to B, from B to A and so on). That's the "un-weighted" part of the OP. If your case differs you'll have to read the docs.

    You can implement an UnDirected graph if you prefer that adding A To B also adds B to A. It can spare some lines of code, but I usually prefer adding all the possibilities myself. Its easier to think "from the Library I can go to aisle A and aisle B. From aisle B to Library and Laboratory", and so on, that trying to think of all edges.

    You can create two tables in a database:

    • Photos (with IDs)
    • Path (IdFrom and IdTo)

    This is easy to maintain and implement.