Przepustowość w grafie.

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;

    }