Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
  • Piet Souris
  • Frits Walraven
  • Carey Brown

dijkstra's algorithm

Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all,
Could somene please help me,
I'm trying to write a program that performs the dijkstra's algorithm, but im clueless on where to begin. I know how it works in theory, but setting up the data types is giving me some trouble, do i use vectors? how can i store a node and information regarding what nodes its linked to with their weights for example
Node Links to (weight)
A B(10) , C(30) , d(34)
B A(10), .........
Is this the correct way to go about it?
Theres a few examples out there but they're really confusing, and i dont want an example thats a gui one.
If anyone can help i'd appreciate it
Ranch Hand
Posts: 118
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'd use a matrix with the x-indexes as "from" and y-indexes ad "to".
so the value at location [a][b] is the distance from a to b.
You could use a negative number as an indicator of an non existant leg.
Then you'd just iterate from the start node and create you'r N*2 dimensional matrix. (distance and last stop).
Sample matrix:
(edited: swapped axis, whoops)

distance A to B is 2, A to C is 2, B to A is 1, B to C is non-existant and so on...
hope this helps.
[ December 18, 2003: Message edited by: Peter Kristensson ]
You didn't tell me he was so big. Unlike this tiny ad:
Thread Boost feature
    Bookmark Topic Watch Topic
  • New Topic