Dijkstra - ścieżka o najmniejszej liczbie węzłów.

Odpowiedz Nowy wątek
2015-01-03 01:08
0

Ma ktoś pomysł jak zmodyfikować typowy algorytm dijkstry, by zamiast ścieżki o najniższym koszcie dojścia z A do B, znajdował ścieżkę o najmniejszej liczbie węzłów (wierzchołków) między A i B, niezależnie od kosztu dojścia.

Liczę na trafne sugestie.

Pozostało 580 znaków

2015-01-03 01:22
5

Nie rozumiem problemu. Niech graf będzie nieważony, tzn każda krawędź ma wagę 1. Wtedy ścieżka o najniższym koszcie będzie właśnie ta najkrótsza, tzn taka która ma najmniej krawędzi. A to oznacza też że ma najmniej węzłów po drodze.


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

Pozostało 580 znaków

2015-01-03 10:48
2

Tylko że w tym przypadku DFS lepiej będzie się sprawował.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2015-01-03 11:10
0

Graf jest grafem ważonym. Załóżmy, że chcemy dojść z wierzchołka A do B. Są dwie drogi z A: Pierwsza -> Z A do D (koszt 10) i z D do B (tez 10). Koszt dojścia tą drogą to 20. Druga -> Z A do E (koszt 1), z E do F (koszt 1) i z F do B (koszta 1). Koszt dojścia A->E->F->B to 3. W tym momencie algorytm dijkstry wybierze drugą drogę, bo ma mniejszy koszt, ale tutaj mijamy po drodze dwa wierzchołki E i F. Natomiast ja chce tak przerobić ten algorytm, by wybierał taką drogę, by po drodze natrafić na jak najmniej wierzchołków, czyli wybrać tą pierwszą. Da się to zrealizować?

@Shalom, tak masz racje, to dobry pomysł.

edytowany 1x, ostatnio: Totalq, 2015-01-03 11:11

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0