Witam natknąłem się na nie lada dla dla mnie problem... Otóż muszę wyznaczyć ścieżkę o maksymalnej przepustowości łączącą wierzchołek o numerze 1 z danym innym wierzchołkiem w grafie oraz wyznaczyć wartość tej przepustowości... Próbowałem algorytmu Forda-Fulkersona lecz on wyznacza tą przepustowość w całym grafie. Czy ktoś ma jakiś ciekawy bądź nie ciekawy oby tylko działający pomysł?
Jeżeli nie potrzebujesz czegoś szybkiego/wyszukanego to da się nawet Dijkstre pod to zaadaptować.
Dijkstre służy do znajdowania najkrótszej ścieżki z punktu do punktu o nieujemnych wagach. W jaki sposób można przerobić taki algorytm żeby sprostał ww wymaganiom?
Przejściu z A do B drogą C:
zamiast: B.koszt=min(B.koszt,A.koszt+C.koszt);
masz: B.przepustowosc=max(B.przepustowosc,min(A.przepustowosc+C.przepustowosc));
reszta taka sama.
Dzięki serdecznie za rozwiązanie:)
Jednak nie potrafię sobie poradzić z przerobieniem tego algorytmu. Oryginalny algorytm. Ktoś podpowie?
public String dijkstra(T v, T w) {
TreeMap<T, Integer> dist = new TreeMap<T, Integer>();
Integer infi = new Integer(9999);
TreeMap<T, Integer> queue = new TreeMap<T, Integer>();
Map.Entry<T, Integer> item;
TreeMap<T, T> prevList = new TreeMap<T, T>();
dist.put(v, 0);
queue.put(v, 0);
for (Map.Entry<T, TreeMap<T, Integer>> eset : tab.entrySet()) {
for (Map.Entry<T, Integer> tmp : eset.getValue().entrySet()) {
if (eset.getKey().equals(v)) {
dist.put(tmp.getKey(), tmp.getValue());
queue.put(tmp.getKey(), tmp.getValue());
} else {
if (!dist.containsKey(tmp.getKey())) {
dist.put(tmp.getKey(), infi);
queue.put(tmp.getKey(), infi);
}
}
}
}
while (queue.size() > 0) {
item = queue.firstEntry();
for (Map.Entry<T, Integer> eset : queue.entrySet()) {
if (eset.getValue() < item.getValue()) {
item = eset;
}
}
queue.remove(item.getKey());
for (Map.Entry<T, TreeMap<T, Integer>> eset : tab.entrySet()) {
for (Map.Entry<T, Integer> tmp : eset.getValue().entrySet()) {
if ((eset.getKey() == item.getKey())) {
Integer dU = dist.get(item.getKey()); //d[u]
Integer wUV = getWeight(item.getKey(), tmp.getKey()); //w(u,v)
Integer dV = dist.get(tmp.getKey());
Integer sumUp = dU + wUV;
System.out.println(sumUp);
if (sumUp < dV) {
dist.put(tmp.getKey(), sumUp);
prevList.put(tmp.getKey(), item.getKey());
}
}
}
}
}
String res = "Przepustowość: " + dist.get(w) + "\n";
return res;
}
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.