Grafikte yerel köprüyü (k) bulmak için en iyi algoritma hangisi olurdu? K derece olan yerel bir köprü, çıkıntısı iki uç noktası arasındaki en kısa mesafeyi en az k olacak şekilde genişleten bir kenardır.LocalBridge of degree in Grafik
Vikipedi: http://en.wikipedia.org/wiki/Bridge_(interpersonal)#Local_bridge
çalıştırın bir all-en kısa yol-maliyetler Floyd-Warshall algoritması gibi algoritma, ancak bunun yerine tipik reel sayılar d arasında mesafeler için dizilerini (d1,d2) kullanın:
d1 en kısa yold2 uzunluğu uzunluğu olduğu İkinci kısa yolFloyd-Warshall algoritmasına Bu modifikasyon basit olmalıdır. Eğer hepsi en kısa yol-maliyetler algoritması çalışan yapılır
, localbridge(k) kenarları bu kenarlar vardır e = {u, v} öyle ki u ve v tatmin d2 >= k arasındaki mesafe (1,d2).
[Floyd-Warshall algoritması] (http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) yeterince iyi mi? – anatolyg
Grafikte tüm yerel köprüler bulmayı düşünüyor musunuz? Belki aklınızda bir (veya iki) belirli düğümler vardı. – phs