[Solved]-Django finding paths between two vertexes in a graph


As you has pointed, this is not a Django/Python related question, but a logical/algorithmic matter.

To find paths between two vertexes in a graph you can use lot of algorithms: Dijkstra, A*, DFS, BFS, Floyd–Warshall etc.. You can choose depending on what you need: shortest/minimum path, all paths…

How to implement this in Django? I suggest to don’t apply the algorithm over the models itself, since this could be expensive (in term of time, db queries, etc…) specially for large graphs; instead, I’d rather to map the graph in an in-memory data structure and execute the algorithm over it.

You can take a look to this Networkx, which is a very complete (data structure + algorithms) and well documented library; python-graph, which provides a suitable data structure and a whole set of important algorithms (including some of the mentioned above). More options at Python Graph Library

Leave a comment