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

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.

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.

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

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ł.