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
}