Dijkstra's Algorithm Concepts and Coding Problems

Question

Question Updated

I am currently working on implementing Dijkstra's Algorithm in Python, I have looked at other questions here regarding the algorithm and none seem to fit what I am looking for.

Currently my program reads two text files, one containing a network routing diagram network.txt (basically the route costs).

0,2,4,1,6,0,0
2,0,0,0,5,0,0
4,0,0,0,0,5,0
1,0,0,0,1,1,0
6,5,0,1,0,5,5
0,0,5,1,5,0,0
0,0,0,0,5,0,0

and one containing the desired route (route.txt)

B>F

The Network Routing Table: (Each Line Is a Node and Its Links so node A is linked to B, C, D and E)

      A  B  C  D  E  F  G

A    [0, 2, 4, 1, 6, 0, 0]
B    [2, 0, 0, 0, 5, 0, 0]
C    [4, 0, 0, 0, 0, 5, 0]
D    [1, 0, 0, 0, 1, 1, 0]
E    [6, 5, 0, 1, 0, 5, 5]
F    [0, 0, 5, 1, 5, 0, 0]
G    [0, 0, 0, 0, 5, 0, 0]

Nodes On The Network: ([Structure] PreviousNode, DistanceFromSource, Visited)

A    [-1, 1000000000, False]
B    [-1, 1000000000, False]
C    [-1, 1000000000, False]
D    [-1, 1000000000, False]
E    [-1, 1000000000, False]
F    [-1, 1000000000, False]
G    [-1, 1000000000, False]

I kind of understand Dijkstra's Algorithm but using the two data structures I have, combined with having to write it in Python I don't have a clue where to go from here because I am unable to get my head round how to do this not knowing the language.

I have some very basic "pseudocode" to what I need to do next

3 - Examine all the unvisited neighbours of the current node and calculate their tentative distances from the starting node, overwriting the existing distance if the new value is lower

4 - Mark current node as visited (will not be examined again)

5 - If not at destination and unvisited node exists go to the unvisited node with the smallest > distance from initial node and make it the current node, otherwise end

6 - Go back to 3

Is anyone able to assist me with translating that "pseudocode" into code or even more meaningful pseudocode would be great as I am struggling with this

I don't know python. Still, If I were you, I would try separating the vocabulary of your specific problem from the algorithm, i.e. separate the details of how you get the data from actually using it. Dijkstra's algorithm actually wants to know edge weights, not how you got those weights. So, write a pseudo code of Dijkstra's and then feed it the information it wants. HTH — Abhijeet Kashnia
– Abhijeet Kashnia, Commented Feb 10, 2012 at 12:50
"complicated versions using graphs etc" -- Dijkstra's algo is an algorithm on graphs, so understanding those is pretty fundamental to getting a good grasp on Dijkstra's. — Fred Foo
– Fred Foo, Commented Feb 10, 2012 at 12:58

Dima Tisnek · Accepted Answer · 2012-02-10 13:01:05Z

2

Use native python "links" between the objects, e.g.:

edges = {1: set([2,3,4]), 2: set([1,5]), ....}
costs = {(1, 2): 99.3, (1, 3): 127.77, ...}

There's no need to create your own classes for such simple problem.

Watch this for inspiration:

http://python.mirocommunity.org/video/1530/pycon-2010-mastering-team-play

edited Feb 10, 2012 at 13:01

answered Feb 10, 2012 at 12:55

Dima Tisnek

11.9k4 gold badges73 silver badges129 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Dima Tisnek Over a year ago

better yet, frozenset() instead of tuple on line 2.

Collectives™ on Stack Overflow

Dijkstra's Algorithm Concepts and Coding Problems

Question Updated

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Question Updated

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related