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 ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

dijkstra's algorithm

 
Greenhorn
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
Regards
Bob
 
Ranch Hand
Posts: 118
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi.
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.
/Peter
[ December 18, 2003: Message edited by: Peter Kristensson ]
 
You didn't tell me he was so big. Unlike this tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
    Bookmark Topic Watch Topic
  • New Topic