[Algorytmika] Rozszerzenie algorytmu Dijkstry

Odpowiedz Nowy wątek
2009-12-30 14:27
hubertus1
0

user image

Cóż - pytanie jest z algorytmiki, ciężko podpiąć to pod konkretny język, dlatego ten dział. Proszę o przeniesienie w razie czego :)

Do rzeczy: do zaprogramowania mam algorytm szukający najkrótszej drogi w grafie. Z pozoru prosta sprawa - Dijkstra. Przeszkoda pierwsza - długość drogi nie jest liczona poprzez sumowanie odcinków, ino po liczeniu procentowych prawdopodobieństw niezależnych zdarzeń. Czyli jeśli mam drogę widoczną na rysunku (1), to długość drogi od 1 do 3 będzie wynosiła 51 [czyli 30 + 30 - ((30*30)/100)]. Prosta sprawa - zmiana warunku w algorytmie - ale to jeszcze nie wszystko :)

Tu nadchodzi druga przeszkoda - bowiem mam znaleźć nie tylko najkrótszą drogę licząc te prawdopodobieństwa, ale również mam odwiedzić jak najmniejszą liczbę krawędzi. Tak więc na obrazku (2) mam drogi 1>2>4>5 oraz 1>2>3>4>5 - obie mają równą długość wg. sposobu liczenia (60.31), ale algorytm Dijkstry zawsze mi zwróci tę "dłuższą" drogę.

Pytanie - jak zmodyfikować algorytm, by po wyliczeniu dwóch dróg o identycznej "długości" brał tę, która odwiedzi minimalną ilość krawędzi? Poniżej moja funkcja w C#:

// MS to macierz sasiedztwa
static int[] Dijkstra(int[,] MS, int n, int from, int to)
        {
            float[] d = new float[n]; // odleglosci
            int[] poprz = new int[n]; // poprzedniki wierzcholkow
            for (int i = 0; i < n; i++)
            {
                d[ i ] = 101;
                poprz[ i ] = -1;
            }
            d[from] = 0;
            List<int> Q = new List<int>(); // lista/kolejka
            for (int i = 0; i < n; i++)
            {
                Q.Add(i);
            }
            while (Q.Count != 0)
            {

                float min = 101;
                int u = -1;
                foreach (int i in Q)
                {
                    if (d[ i ] < min) { min = d[ i ]; u = i; }
                }
                if (u == -1) break;
                Q.Remove(u);
                for (int i = 0; i < n; i++)
                {
                    if (MS[u, i] == -1) continue;
                    int v = i;
                    int c = MS[u, i];
                    if (d[ u ] + c - ((c * d[ u ]) / 100) < d[v])
                    { // liczenie prawdopodobienstwa
                        d[v] = d[ u ] + c - ((c * d[ u ]) / 100);
                        poprz[v] = u;
                    }
                }
            }
            Console.WriteLine(d[to]); // wypisanie dlugosci drogi
            return poprz; // zwrocenie poprzednikow
        }

Pozostało 580 znaków

2009-12-30 16:53
0x200x20
0

Najpierw wystarczy znależć wszystkie najkrótsze ścieżki z A do B pod względem długości (w twoim przypadku prawdopodobieństwa) a potem wybrać drogę, która ma najmniej krawędzi.
Żeby znaleźć wszystkie najkrótsze drogi z A do B wystarczy zapuścić Dijkstre (która znajdzie najkrótsze drogi od A do wszystkich wierzchołków grafu) a potem przejść się po wszystkich wierzchołkach sąsiadujących z B i sprawdzić czy przypadkiem długość drogi od wierzchołka A do B przez dany wierzchołek sąsiadujący z B nie jest równa długości najkrótszej drogi. Gdy masz już wszystkie najkrótsze drogi pod względem prawdopodobieństwa nie jest problemem wybrać tą z najmniejszą ilością krawędzi.

Pozostało 580 znaków

2010-01-02 13:52
yyy
0

a mi sie zdaje e zadzialalo by cos na zaszadzie listy kierunkowej gdzie bedzie sie prawdzalo ile przejsc jest z A do C czy nie ma tam B po drodze

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