The shortest distance between Atlanta and Chicago is 729 miles. The route is Atlanta -> Birmingham -> Meridian -> Jackson -> Shreveport -> Dallas. The shortest distance between Atlanta and Dallas is 791 miles. The route is Atlanta -> Spartanburg -> Charlotte -> Greensboro -> Petersburg -> Richmond -> Washington -> Baltimore -> Philadelphia -> Newark -> New York. The shortest distance between Atlanta and New York is 897 miles. So, I decided to actually compute the shortest paths from Atlanta to Dallas, Chicago, and New York. Represent the highway system as a graph, and then you can apply Dijkstra’s algorithm to solve your problem.Īt this page, I found “a data file that represents a significant portion of the interstate highway system”. So, for example, let’s say that you are in Atlanta, and you want to find the quickest routes to Dallas, Chicago, and New York. In the single-source shortest path problem, you are given a graph and some distinguished vertex, and you want to find the shortest paths between the distinguished vertex and every other vertex in the graph. A binary heap is a complete binary tree that is ordered such that, for any given vertex, all of the vertex’s children have lower priority than it.ĭijkstra’s algorithm solves the single-source shortest path problem. Priority queues are commonly implemented as binary heaps, and that is how I implemented my priority queue. A stack is a priority queue where elements have more precedence the later they enter the container. A queue is a priority queue where elements have more precedence the earlier they enter the container. You can actually think of stacks and queues as types of priority queues. The item that has the highest priority is the item that gets removed. In Dijkstra’s algorithm, the data structure is a priority queue. The last item that you put into it is the first item that you remove from it. In depth-first search, the data structure is a stack. The first item that you put into it is the first item that you remove from it. In breadth-first search, the data structure is a queue. One of the many interesting things that I learned from my artificial intelligence class is that the big difference between breadth-first search, depth-first search, and Dijkstra’s algorithm is the data structure that stores the vertices. Python implementation of Dijkstra’s algorithm.Python implementation of the priority queue.Java implementation of Dijkstra’s algorithm.Java implementation of the priority queue.In this case, I implemented Dijkstra’s algorithm and the priority queue in Python and then translated the code into Java. Oftentimes there’s a better tool for the job, but I like to use Python when I can. Consequently, it is quick and fun to develop in Python. Python is a clean, easy-to-use language that has a REPL. So, today I bring to you a reinvention of the wheel.Įspecially when the project is small, I tend to develop software in Python and then translate the code into another language. Although I’ve implemented variants of Dijkstra’s algorithm in the past, I wanted to implement the algorithm using my own implementation of the priority queue.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |