implmentere Dijkstra i c++

Min java-agtige pseudo-kode:


int INIFINITE_DISTANCE = 32000;

/***************************************************************/

//    S: (Listen med de ordnede noder/rooms):
private static Set settledNodes = new HashSet();

boolean dijkstra::isSettled(room r)
{
    return settledNodes.contains(v);
}



/***************************************************************/

//    d: (Listen med de kortest afstande):

/* Vores Map skal indeholde gemme den korteste
* afstand til hver enkelt node/room. Da alle
* objekter benytter samme Map, har vi erklæret
* det som værende static:*/
private static Map shortestDistances = new HashMap();


void dijkstra::setShortestDistance(room r, int distance)
{
    shortestDistances.put(r, new integer(distance));
}

int getShortestDistance(room r)
{
    integer d = (int) shortestDistances.get(r);
    return (d == NULL ? INIFINITE_DISTANCE : d.intValue();
}

/***************************************************************/


// previous:    (den forrige korteste vej - kaldes også "predecessor")
                               
/* Map der indeholder relationen/afstanden mellem 2 noder/rooms. Reelt
* vil det være en given nodes "forrige korteste vej til en anden node/room".
* Da vi også her kun indsæter én kopi af en given key, har vi ligeledes her
* gjort brug af et Map:*/

private static Map predecessors = new HashMap();


//    Opdaterer værdien af den "forrige kortest vej til noden":
private void setPredecessor(room *a, room *b)
{
    predecessors.put(a, b);
}

private void getPredecessor(room *a, room *b)
{
    predecessors.put(a, b);
}



/***************************************************************/

//    Q:    (de Usorterede noder)

/* Da vi har brug for en datastruktur, hvor vi kan lave oplag på et
* givent room/node som nøgle, og ud fra denne finde den nuværrende
* korteste afstand - givet ved d(), anvender vi et Set.
* Vi kunne have valgt at indsætte vores "predecessors" i et almindeligt
* Set, og sortere det efter d() ("den estimerede korteste afstand") efter
* HVER iteration, for at finde det room/node, hvortil der den korteste afstand. */

private static SortedSet unsettledNodes = new TreeSet(shortestDistanceComparator);

/* Men fordi det er en meget iterativ process, har vi valgt at sortere vores Set
* i det vi indsætter de forskellige noder/rooms i set'et.
* Vi har derfor valgt at gøre brug af et SortedSet, hvor vi har mulighed for at
* sortere elementerne ved brug af en Comparator().
* Dvs. at vi har lavet en "comparator" til at sortere vores noder/rooms (elmenterne i set'et).*/

private static Comparator shortestDistanceComparator = new Comparator()
{
    /* Vi bruger comparato i "sortedSet" til at afgøre begge objekters "nummer-orden"
    * og identitet. Hvis vores comparator returnerer at to elementer er lig hinanden,
    * går vores Set ud fra, at de to er ens, og gemmer kun én instans af elementet (vores room).
    * For at forhindre at miste/slette rooms hvortil afstanden er den samme, sammenligner
    * vi SELVE Set-elementerne. */

    public int compare(Object left, Object right)
    {
        int shortestDistanceLeft    = getShortestDistance( (room) left);
        int shortestDistanceRight    = getShortestDistance( (room) right);

        if(shortestDistanceLeft > shortestDistanceRight)
            return +1;
        else if(shortestDistanceLeft < shortestDistanceRight)
            return -1;
        else // de er lig hinanden
            return ( (room)left).compareTo(right);
    }//compare

};


private room extractMin()
{
    //    Først finder vi noden/room'et med den korteste afstand:
    room r = (room) unsettledNodes.first();

    //    ...og derefter fjerner vi den/det fra vores usorterede set.
    unsettledNodes.remove(r);
    return r;
}




/***************************************************************/

public void doDijkstra(room *start, room *target)
{
    while(!unsettledNodes.isEmpty())
    {
        //    Hent det room, hvor til der er den korteste afstand:
        room r = extractMin();

        //    Hcis vi har nået vores "target":
        if(r == target)
            break;

        settledNodes.add(r);

        FindNeighbors(r);
    }//while

}//doDijkstra()

Er det en skole opgave eller hvad ?
http://eksperten.dk/spm/500636

Yep - i hvert faldet her - for moi ! ...men det er ikke et krav at vi implementerer Dijkstra.

...men det vil jeg selvfølgelig rigtig gerne.

Har stået og skrevet pseudo-kode på en tavle hele dagen, for at fatte hvordan fanden Deijkstra fungerer, men jeg fatter hat og briller når det gælder brugen af HashMaps, Set's etc i c++.

Så please, soreno - help me ;-)

Findes der en opgavebeskrivelse som jeg kan se ?

Hvordan repræsenterer i en graf (adjacency list eller matrix) ?

(Det skulle *ikke* have været et svar!)

tjooo....
Opgaveformuleringen er:

Vi befinder os i eventyr, bestående af felter, spillere, prinsesse og væsener



Felter  Er som i f. eks. i skak eller lignende spil, hvert felt har et navn, en beskrivelse, samt op til 4 exit muligheder til andre felter i  eventyr. Det er sådan at der fra et felt til et andet felt er en afstand i km Ét af felterne er et slot med en prinsesse, der er ulykkelig fanget.



Spilleren Spilleren rejser rundt i eventyr, med det formål, at finde og befri prinsessen på kortest mulig tid og uden selv at miste livet eller modet.

Spilleren er udstyret med modstandskraft (overfor fjendens angreb) og udholdenhed (til at kæmpe længst muligt). Disse egenskaber kan mistes helt eller delvis ved møde med væsener. Spilleren kan også være heldig at øge udholdenhed og modstandskraft, hvis han/hun møder et venligt væsen. Spilleren er endvidere udstyret med et ur, så  hun/han altid ved hvad klokken er.

Væsener I eventyr er der, som nævnt væsener, orker, féer, trolde, andre, disse har nogle egenskaber, der kan være negative eller positive for de deltagende spillere. Også væsenerne befinder sig også på felterne, men det er uforudsigeligt, hvornår de befinder sig på hvilke felter.

Opgaven skal løses som et tekst-løsning (i et Dos-vindue) - en grafisk løsning er ikke et krav.

Spillet er slut, når en vis tid er gået, der udskrives en status for spilleren.


Vi skal ikke nødvendig vise "grafen", men derimod kun kunne fortælle spilleren, hvilken vej der er kortest...

Mon ikke det vil blive betragtet som snyd hvis du får hjælp her ?

Nooope....

Vi er ikke blevet undervist i SP-algoritmer, grafer etc... Og vi skal som sagt ikke implementere Dijkstra, hvilket vi dog har tænkt os at gøre alligevel - men efter som at vi kun har rodet med c++ i en 3 ugers tid, er vi desværre af (jeg er ked at indrømme det) nød til at søge lidt hjælp... ;o)

Jeg har lavet en lille eksempel på hvordan man kan finde den korteste vej gennem en labyrint. Det er lidt langt så jeg har lagt det her:

http://home20.inet.tele.dk/midgaard/snip/hunt.html

Labyrinten (Maze) er defineret med vægge og gange, den ene 2 tal i Maze[][] er målet.
I main() er der et kald til FindPath(...) de to første parametre angiver hvor man starter.

Hvis labyrinten bliver meget stor vil algoritmen blive for ineffektiv, den vil gå i ring for mange gange.

Labyrinten og den valgte sti vil blive vist grafisk. Sørg for at vinduet har mindst 30 linier når du tester.

Hej Bertel !

Tak for linket - men jeg fik det dog selv implementeret den igår aftes ;o)

...men efter at have set din kode, må jeg sgu indrømme at det kunne gøres på en anelse mere elegant måde, så du skal mange tak for din meget konkrete hjælp.

Ligger du lige er svar !!

Jeg forsøger at undgå point.

Rydder lidt op...

uanset hvad skal du have mange tak for hjælpen, Bertel...

soreno >> 1000 tak fordi du gad at bruge tid på at kigge lidt på det, men jeg fik som sagt selv løst mit mindre problem (som det viste sig at være) ;o)