I have to implement Dijkstra's Algorithm in Python for a homework assignment. It's due tomorrow and I'm currently totally lost. I just started learning Python on Sunday, and I've never actually implemented Dijkstra's algorithm before.

I can Google up some code, but I don't understand the code (and I'm not just going to copy-paste, what would I learn from that?)

The specific problems I'm having are:

1) Representing the data in Python. He gave us a graph with a number of vertices and weights on the paths between them. I'm not sure how to put this into code, including the vertices and the paths with their weights.

2) Implementing the actual algorithm to go through the vertices and find the shortest path between two points.

Any help would be greatly appreciated.

Also, Python is totally awesome.

Yes I can! I spent about six hours learning Python on Sunday, and it was the best six hours I've spent at my computer all year.

Life's too short. Just look at the pseudo code in wikipedia and compare with the code below. It's always best to learn by diving in.

It's called re-use

http://www.python.org/doc/essays/graphs.html

It says there:
A -> B
A -> C
B -> C
B -> D
C -> D
D -> C
E -> F
F -> C

This graph has six nodes (A-F) and eight arcs. It can be represented by the following Python data structure:

graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']}

Use that as a reference to make yours.the weights can be attached to the vertices if you put instead of 'B' in 'A'=['B','C'] sth like a dictionary or a list that has in the first field 'B' and in the second the weight.

See in the link how to traverse and access the fields of the graph and then find out how to traverse the inner structs that contain the name of the vertex and weight and the rest is just the translation of the algorithm in code which if you know and understand what it does won't be that difficult.might take some hours but you can do it.

I got your program to work but I will refrain from posting the answer because you should do your own homework, but I will post it after its due (tommorow?). Your problem lies in not checking if two nodes are neighbors.

When I first learned Dijkstra's I drew it out by hand. Pen and pencil are unbeatable methods for learning.

Basically, with this algo, you have sort of a "wave front". each point on this wave front is a node in a queue. This queue is sorted by "cost".. basically the cheapest points are first and the most expensive are last. This cost is usually cumulative. Every time you pull a point off the cue, you compute the costs (distances) to all of its neighbours and throw it on the queue. To make sure you dont go in circles, you mark visited queues so you make sure you dont check them again.

Not really - It depends on the problem. A* will find the same (ie best) solution assuming that the heuristic used is admissible. And it usually does it a lot faster (if the heuristic is good).

If the heuristic used is conservative, meaning it will always be equal or lower than the actual path, A* will find the best path as well. An example of a conservative heuristic useful for navigation (in a game for example) would be distance.

This is because a node is only closed after it's been evaluated as the lowest cost+heuristic in the open list (and the best path is found when the target node is closed). Dijkstras alone can (and will) waste a lot of time searching the opposite side of the "playing field" for example, since there is no concept of a goal in that algorithm.

There are lots of techniques you can use to improve the speed of A* (or any path finding algorithm really).
Not calculating the path at every AI update is pretty obvious - only recalculate the path if the target (or something else that is meaningful in the particular problem) changes.

Another benefit of A* is that you can lock it to a certain number of "steps" and get a "maybe good" partial path.

That's true. But going from two ends at once is pretty much like adding a heuristic, only still a lot slower and a fair bit more work

The difference between Dijkstra's and A* is like 25 lines of code. So if it's possible to implement it, I don't see any reason why you should not.

I'm not sure why your implementation works when you check all the nodes in the graph and not just the neighbors of the node that currently has the lowest length.