최대 무게가 최소 인 경로 찾기

Question

나는 방향을 잡은 그래프를 통해 경로를 찾는 알고리즘을 찾으려고합니다. 기존의 경로가 아니며 이미 완료된 것과 같은 참조를 찾을 수 없습니다.

최대 최소 무게를 가진 경로를 찾고 싶습니다.

e.e. 가중치가 10 -> 1- 10 및 2-> 2-> 2 인 두 개의 경로가있는 경우 최소 가중치 (2)가 첫 번째 경로의 최소 가중치 (1)보다 크기 때문에 두 번째 경로가 첫 번째 경로보다 우선합니다). 사람이 할 수있는 방법을 작동하거나 일부 참고 자료의 방향으로 날 지점 수 있다면

는 믿을 수 없을만큼 :) 유용

편집 될 :: 내가 난 것을 언급하는 것을 잊었다 보인다 특정 정점에서 다른 특정 정점으로 가려고합니다. 여기서 중요한 점은/

EDIT2 :: EDIT2 :: 지적한 바와 같이 가장자리의 가중치가 음수가 아닌 것을 강조해야합니다.

Answer 1

Prim's 또는 Kruskal's 알고리즘을 사용하십시오. 당신이 물어 본 정점이 연결되어 있음을 알게되면 멈추도록 수정하십시오.

EDIT : 최대 값은 최소이지만 최대 값은 원하는 것처럼 보입니다. 최소의 경우 Kruskal 알고리즘은 작동하지 않습니다.

편집 : 예는 괜찮습니다. 제 잘못입니다. 그러면 Prim의 알고리즘 만 작동합니다.

Answer 2

"답변에 대한 이진 검색"패러다임을 사용할 수도 있습니다. 즉, 각 가중치를 테스트하여 가중치에 대해 이진 검색을 수행하면 w보다 큰 가중치 만 사용하여 그래프에서 경로를 찾을 수 있는지 여부를 확인합니다.

w (이진 검색을 통해 찾을 수 있음)은 답변을 제공합니다. 경로가 존재하는지 확인하기 만하면되므로, 최단 경로가 아니라 너비 우선/깊이 우선 검색 O (| E |) 검색 만하면됩니다. 따라서 Dijkstra/Kruskal/Prim의 O(|E|log |V|)에 필적 할만한 것은 O(|E|*log(max W))입니다. (그리고 나는 그 증거도 바로 볼 수 없습니다.)

Answer 3

그러나 이것은 당신이 변화를 필요 BFS 스타일의 알고리즘을 사용하여 해결할 수 있습니다

• "방문"각 노드를 표시, 당신은 당신이 도달하는 데 걸린 경로를 따라 최소 중량을 표시하는 대신 그것.

예를 들어, I와 J가 인접한 경우 I의 값은 w1이고 그 사이의 가장자리의 무게는 w2이고 J = min (w1, w2)입니다.

• 값이 w1 인 마킹 된 노드에 도달하면 새 값 w2 (및 w2> w1)를 지정하는 경우 다시 마킹하고 처리해야 할 수 있습니다. 이것은 모든 최소값의 최대 값을 얻는 데 필요합니다.

예를 들어 I와 J가 이웃하는 경우 I의 값은 w1이고 J의 값은 w2이며 그 사이의 가장자리의 무게는 w3이고 min (w2, w3)> w1 인 경우 J 이웃의 모든 것을 다시 처리하십시오.

는

Answer 4

, 그냥 시도하고 내가 여기에 게시하기 전에 일 임시 솔루션을했다 피드백을 조금 얻을 여기 내 자신의 질문에 대답 좋아

: 각 노드는 "경로 조각을"저장

을이 전체입니다 지금까지의 경로.

0)는 시작 정점
1)이 정점에서 모든 경로 단편을 생성하고, 우선 순위 큐
2) 상부 오프 우선 순위 큐 오프 단편을 취할 추가 및 전류를 설정 전류 정점 세트 현재의 정점 대상 정점 경우 해당 경로
3)의 종료 정점에 정점 후, 나는이 비록 최적의 경로를 찾을 것입니다 확실하지 않다
4) 고토 1

을 경로를 반환 3 단계의 종료 조건이 조금 야심적이라고 생각합니다. 이 알고리즘은 정점을 닫지 않기 때문에 정점이 닫히지 않을 때까지 (정점은 여러 경로 조각을 참조 할 수 있기 때문에) 더 나은 종료 조건을 생각할 수 없습니다. 모든 정점이 닫힐 때까지 기다릴 수 없습니다 (예 : Dijkstra 's 예)

Answer 5

Dijkstra 's를 계속 사용할 수 있습니다!

+를 사용하는 대신 min() 연산자를 사용하십시오.
또한 힙/priority_queue의 방향을 지정하여 가장 큰 항목이 맨 위에 오도록 할 수 있습니다. 이 같은

뭔가 작업을해야합니다 : (내가 아마 구현 세부 사항을보고 싶었어)이 감소 모든 가능성을 찾을 수 있기 때문에

let pq = priority queue of <node, minimum edge>, sorted by min. edge descending 
push (start, infinity) on queue 
mark start as visited 
while !queue.empty: 
    current = pq.top() 
    pq.pop() 
    for all neighbors of current.node: 
     if neighbor has not been visited 
      pq.decrease_key(neighbor, min(current.weight, edge.weight)) 

(당신이 노드에이를 때마다 최적의 경로를 따랐다 보장 순서와 가장자리를 추가하여 경로를 향상시킬 수 없어)

시간 제한은 Dijkstra 's - O (Vlog (E))와 동일합니다.

편집 : 오, 이건 기본적으로 당신이 게시 한 것입니다. LOL.

Answer 6

저는 Prim이 여기서 작동 할 지 확신하지 못합니다. 이 반례를 가지고 :

V = {1, 2, 3, 4} 

E = {(1, 2), (2, 3), (1, 4), (4, 2)} 

weight function w: 
    w((1,2)) = .1, 
    w((2,3)) = .3 
    w((1,4)) = .2 
    w((4,2)) = .25 

당신이 maxmin 거리가 4까지가는 경로를 달성하는 동안, 1 --> 2 --> 3 경로를 선택합니다 일부터 1 ~ 3에 maxmin 경로를 찾을 수 프림 적용합니다.

Answer 7

나는 this 대답을 복사하고 및 알고리즘에 대한 정확성 내 증거를 추가도 추가 :

내가 Dijkstra's의 일부 변종을 사용합니다.나는 위키 백과에서 바로 아래 의사 코드를 가져다가 5 작은 것들 변경 :

가 초기화 (에 3 행에서) distwidth로 명칭 변경

1. 을
2. 의 폭을 초기화 width (3 호선) -infinity에 각 infinity 원본 (8 행)의
3. 는
4. 업데이트 기능과 기호를 수정 -infinity (라인 14)에 마무리 조건 설정 (라인 20 + 21)
01,235,164

1 function Dijkstra(Graph, source): 
2  for each vertex v in Graph:         // Initializations 
3   width[v] := -infinity ;        // Unknown width function from 
4                 // source to v 
5   previous[v] := undefined ;        // Previous node in optimal path 
6  end for              // from source 
7  
8  width[source] := infinity ;         // Width from source to source 
9  Q := the set of all nodes in Graph ;      // All nodes in the graph are 
10                 // unoptimized – thus are in Q 
11  while Q is not empty:          // The main loop 
12   u := vertex in Q with largest width in width[] ;  // Source node in first case 
13   remove u from Q ; 
14   if width[u] = -infinity: 
15    break ;           // all remaining vertices are 
16   end if             // inaccessible from source 
17   
18   for each neighbor v of u:        // where v has not yet been 
19                 // removed from Q. 
20    alt := max(width[v], min(width[u], width_between(u, v))) ; 
21    if alt > width[v]:         // Relax (u,v,a) 
22     width[v] := alt ; 
23     previous[v] := u ; 
24     decrease-key v in Q;       // Reorder v in the Queue 
25    end if 
26   end for 
27  end while 
28  return width; 
29 endfunction 

이 작품 왜 일부 (handwaving) 설명 : 당신이 소스로 시작합니다. 거기에서, 당신은 그 자체로 무한한 능력을 가지고 있습니다. 이제 소스의 모든 이웃을 확인합니다. 가장자리의 용량이 모두 같지 않다고 가정합니다 (예 : (s, a) = 300). 그러면 b에 도달하여 (s, b)을 통해 더 좋은 방법이 없기 때문에 가장 좋은 경우 용량은 b입니다. 모든 정점에 도달 할 때까지 알려진 정점 집합의 가장 가까운 이웃으로 계속 이동합니다. 알고리즘의 정확성

증명 : 알고리즘의 임의의 지점에서

는 정점 A와 B의2 세트가있을 것이다. A의 정점은 올바른 최대 최소 용량 경로가 발견 된 정점이됩니다. 그리고 세트 B는 우리가 답을 찾지 못한 꼭지점을 가지고 있습니다.

유도 성 가설 : 어떤 단계에서 세트 A의 모든 정점에는 올바른 최대 최소 용량 경로 값이 있습니다. 즉, 모든 이전 반복이 정확합니다.

기본 경우의 정확도 : 집합 A에 정점 S 만있는 경우. 그러면 S 값은 무한대가됩니다. 현재 반복에서

, 우리

설정

브로 [W] = 최대 (브로 [W], 분 (브로 [V], width_between (VW)))

유도 단계 : W가 가장 큰 val [W] 인 집합 B의 꼭짓점이라고 가정합니다. W는 대기열에서 대기열에서 제외되고 W는 응답 값 [W]으로 설정됩니다.

이제 모든 다른 S-W 경로의 너비는 < = val [W]임을 보여 주어야합니다. W에 도달하는 다른 모든 방법은 집합 B의 다른 꼭지점 (X라고 함)을 통과하기 때문에 항상 적용됩니다.

집합 B의 다른 모든 정점 X의 경우 val [X] < = val [ W]

따라서 W에 대한 다른 경로는 val [X]에 의해 제한되며 val [W]보다 클 수 없습니다.

따라서 val [W]의 현재 추정값이 최적이므로 알고리즘이 모든 꼭지점에 대해 올바른 값을 계산합니다.