Algorytmy znajdowania ścieżki

Cześć! Znacie może jakiś szybki algorytm znajdowania "najmniej ważącej" ścieżki w grafie ważonym między dwoma wierzchołkami (tylko i wyłącznie między tymi dwoma, są one sprecyzowane na wejściu) z takim ograniczeniem, że wagi krawędzi to 0 lub 1? Najlepiej żeby to było szybsze niż Dijkstra na kopcach (czyli szybsze niż O(E * log V).

Tak to tylko w erze ;) Jeśli wiesz coś o tym grafie to A* z odpowiednia heurystyką będzie szybsza.

Nie wiem czy rozumiem pytanie do końca - każda krawędź ma wagę 0 albo 1 i szukasz ścieżki o najmniejszej wadze między dwoma wybranymi?

Kolejne podejście (pseudokod):

def find_shortest_path(graph, start, end):
    candidates = [start]
    path_len = -1
    while not candidates.empty():
        queue = candidates
        candidates = []
        path_len += 1
        while not queue.empty():
            next = queue.dequeue()
            if next.visited:
                continue;
            next.visited = True
            if next == end:
                return path_len
            for edge in next.edges:
                if not edge.dest.visited:
                    if edge.weight == 1:
                        candidates += [edge.dest]
                    else:
                        queue.enqueue(edge.dest)
    return 666  # nie znaleziono

Po poprzedniej pomyłce (przed edycją) nie wiem czy nie zepsułem czegoś znowu, ale pomysł jest taki:
Jako że są tylko wagi 1 i 0, to wiadomo że najlepiej przejść po samych krawędziach o wadze 0. Jeśłi się nie da, to może da się to zrobić wykorzystując tylko jedną krawędź o wadze 1. Itd, itd. Więc algorytm działa tak:

• ustawiasz długość ścieżki na 0 (w kodzie na -1, bo długość jest inkrementowana na początku - taki szczegół implementacyjny)
• idziesz tak daleko jak się da po krawędziach o wadze '0', a te do których prowadzi krawędź o wadze '1' zapisujesz do pomocniczej tablicy
• jeśli doszedłeś do wierzchołka końcowego, zwracasz długość ścieżki. Jeśli nie, zwiększasz długość ścieżki, i powtarzasz poprzedni krok zaczynając od wierzchołków do których prowadziły krawędzie o długości '1'.

(Złożoność O(E))

Weź normalnego Dijkstre tylko że z dwoma kolejkami.
Przejścia o wadze 0 - do pierwszej, o wadzę 1 - do drugiej.
Najpierw "opróżniasz" tą pierwszą.