Speicherung von Entfernungsinformationen (Dijkstra-Algor.)

WaRRiE

Hallo zusammen,

ich möchte mit dem Djikstra Algorithmus ein kleines Tool mit GUI Oberfläche in C++ schreiben. Das Programm soll mit dem Algorithmus Entfernungen zwischen 2 Orten berechnen. Jetzt habe ich das Problem, dass ich etwas auf dem Schlauch stehe wie ich die ganzen Daten speichern soll, die das Programm benötigt.

Als Beispiel mal eine Zeichnung von Wikipedia dazu:

http://de.wikipedia.org/wiki/Bild:DijkstraStep01.svg

Ich weiss von jeden Knoten aus, wie weit es zum nächstmöglichen Knoten ist. Heisst, von Frankfurt aus komme ich direkt nach Mannheim, Würzburg und Kassel. Dazu weiss ich noch die Entfernung zu dem jeweiligen nächsten Knoten. Daraus kann man sich dann eine kleine Matrix zusammenbasteln und in einer Tabelle festhalten. Nur: wie speichere ich das am besten im Programm ab? In Array(s)? Eine verkettete Liste? Ich könnte mir ein Array anlegen, pro Stadt. Sprich:

String data[] = {"Frankfurt", "Mannheim", "85", "Würzburg", "217"} usw. ...

Ob das dann zu Problemen mit dem Dijkstra Algorithmus führen würde, weiss ich jetzt (noch) nicht. Ich glaube aber auch dass das keine schöne Umsetzung wäre.

Lange Rede, kurzer Sinn: da ich wirklich auf dem Schlauch derzeit stehe, kann mir jemand einen Denkanstoss geben, wie ich das ganze im Quellcode abspeichern könnte?

Ein fragender,
WaRRiE

PS: Ich danke schon mal!

Kuldren

Wie wärs mit ner Klasse Node die alle Attribute speichert und dann einfach eine Liste aus Nodes

In Wikipedia ist das eh alles gut beschrieben...

Alternativ auch hier: http://mandalex.manderby.com/d/dijkstra.php

drakon

Da könnte in etwa so aussehen:

struct city
{
 int kosten;
 std::vector<city*> citys;
};

Dann kannst du das ganz einfach rekursiv befüllen und Fertig.

Kuldren

drakon schrieb:

Da könnte in etwa so aussehen:
struct city
{
 int kosten;
 std::vector<city*> citys;
};
Dann kannst du das ganz einfach rekursiv befüllen und Fertig.

jop...
das gute an dieser konstruktion ist dass man später ohne große umstände weitere informationen zu den städten hinzufügen kann - falls benötigt

WaRRiE

Vielen Dank für eure Hilfe.