Avatar billede arriva Nybegynder
25. april 2007 - 16:53 Der er 1 løsning

Dijkstra's algoritme

Hej folkens

har lidt problemer med Dijkstra's algoritme i en opgave. Bliver bedt om at give et eksempel på en acyklisk orienteret graf som har mindst én kant af negativ vægt for hvilken Dijkstra's algoritme giver det forkerte svar.

Jeg har prøvet noget a la:

En graf med 3 vertex, s er source.
V = {s,a,b}
E = {(s,a),(s,b),(b,a)}
w = {1,2,-2}

men jeg syntes stadigvæk det bliver rigtigt? :(
Avatar billede arriva Nybegynder
25. april 2007 - 17:26 #1
Nå, følgende giver et eksempel på en graf hvor det ikke virker:

V = {s,a,b,c}
E = {(s,a),(s,b),(a,b),(b,c)}
w = {2,1,-3,2}

Lukker igen.
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
IT-kurser om Microsoft 365, sikkerhed, personlig vækst, udvikling, digital markedsføring, grafisk design, SAP og forretningsanalyse.

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester