A friend of mine who studies Operations Research in Transportation Engineering suggested that I look into the problem of path optimization subject to one or more constraints and provided me with a paper he wrote some time ago. I perused the documents and was fascinated by the topic. Following some internet research, I thought that I could start by trying to implement a shortest path algorithm known as Dijkstra's algorithm.
This is a python implementation of Dijkstra's optimal path algorithm using a adjacency matrix from a csv file. The direction of travel is row to column. Inaccessible path is represented by a distance of 1000. Given a starting node, the program looks for its neighbor nodes and for each, calculates and stores the distance from the starting node and its index. Similarly, for each of the neighbor nodes, their neighboring nodes are sought in turn and the shortest cumulative distance to each from all possible routes to them along with the corresponding parent node index is stored. This process is continued until all the nodes have been visited. In the end, each node has two important pieces of information attached: the parent node corresponding to the optimal path and the optimal total distance to the node from the origin/starting node.
This way of going about the shortest route problem is based on this explanation which I found very helpful.
These Google Maps pictures with the assignment of nodes from 1 to 15 have been directly excerpted from my friend's paper.
Code @ GitHub
This is a python implementation of Dijkstra's optimal path algorithm using a adjacency matrix from a csv file. The direction of travel is row to column. Inaccessible path is represented by a distance of 1000. Given a starting node, the program looks for its neighbor nodes and for each, calculates and stores the distance from the starting node and its index. Similarly, for each of the neighbor nodes, their neighboring nodes are sought in turn and the shortest cumulative distance to each from all possible routes to them along with the corresponding parent node index is stored. This process is continued until all the nodes have been visited. In the end, each node has two important pieces of information attached: the parent node corresponding to the optimal path and the optimal total distance to the node from the origin/starting node.
This way of going about the shortest route problem is based on this explanation which I found very helpful.
 |
| Optimal path from node 2 to node 15 |
 |
| Manual Dijkstra iteration along with content from the aforementioned paper on the topic |
These Google Maps pictures with the assignment of nodes from 1 to 15 have been directly excerpted from my friend's paper.
Code @ GitHub
No comments:
Post a Comment