Encontrar o caminho com o peso máximo mínima

Question

Eu estou tentando descobrir um algoritmo para encontrar um caminho através de um grafo direcionado. Não é um caminho convencional e não consigo encontrar quaisquer referências a qualquer coisa como esse ser feito.

Eu quero encontrar o caminho que tem o peso máximo mínimo.

i. Se existem dois caminhos com pesos 10-> 1-> 10 e 2-> 2-> 2, em seguida, o segundo percurso é considerado melhor do que o primeiro, porque o peso mínimo (2) é maior do que o peso mínimo da primeira (1 ).

Se alguém pode descobrir uma maneira de fazer isso, ou apenas me apontar na direção de algum material de referência que seria extremamente útil:)

EDIT :: Parece que eu esqueci de mencionar que eu estou tentando obter a partir de um vértice específico para outro vértice específico. Muito ponto importante lá: /

EDIT2 :: Como alguém abaixo fora pontas, devo destacar que pesos das arestas são não negativo.

Answer 1

Use um de Prim ou algoritmo de Kruskal. Apenas modificá-los para que eles parar quando eles descobrem que os vértices que você perguntar sobre são conectados.

EDIT: Você pede para o máximo mínimo, mas seus exemplos parece que você quer máximo mínimo. No caso do algoritmo de máxima mínima de Kruskal não vai funcionar.

EDIT: O exemplo é bom, o meu erro. Apenas o algoritmo de Prim vai funcionar então.

Answer 2

Estou copiando esta resposta e acrescentando também adicionando a minha prova de correção para o algoritmo:

Gostaria de usar alguma variante do de Dijkstra. Peguei o código pseudo abaixo diretamente da Wikipedia e só mudou 5 pequenas coisas:

1. dist renomeada para width (da linha 3 por diante)
2. inicializado cada width para -infinity (linha 3)
3. inicializado a largura da fonte de infinity (linha 8)
4. Definir o critério de chegada para -infinity (linha 14)
5. Modificado a função de atualização e sinal (linha 20 + 21)

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

Alguns (handwaving) explicação de por que isso funciona: você começa com a fonte. De lá, você tem capacidade infinita para si. Agora você verificar todos os vizinhos da fonte. Suponha que as bordas não têm todos a mesma capacidade (no seu exemplo, dizer (s, a) = 300). Então, não há melhor maneira de chegar b então via (s, b), para que você saiba a melhor capacidade caso de b. Você continua indo para os melhores vizinhos do conjunto conhecido de vértices, até chegar a todos os vértices.

prova de correção do algoritmo:

Em qualquer ponto no algoritmo, haverá 2 conjuntos de vértices A e B . Os vértices em A serão os vértices a que foi encontrado o caminho capacidade mínima máxima correcta. E um conjunto B tem vértices para os quais não tenham encontrado a resposta.

indutivo Hipótese : Em qualquer etapa, todos os vértices em conjunto A tem os valores corretos de caminho máxima capacidade mínima para eles. ie., todas as iterações anteriores estão corretas.

Correção de caso-base : Quando o conjunto A tem o vértice apenas S. Em seguida, o valor de S é infinito, o que é correto.

Em iteração atual, montamos

val [W] = max (val [W], min (val [V], width_between (V-W)))

passo indutivo : Suponhamos que, W é o vértice no conjunto B com o maior val [W]. E W é retirado da fila da fila e W foi definido a resposta val [W].

Agora, precisamos mostrar que qualquer outro caminho S-W tem uma largura <= val [W]. Esta será sempre verdade, porque todas as outras formas de alcançar W vai passar por algum outro vértice (chamemos-lhe X) no conjunto B.

E para todos os outros vértices X em conjunto B, val [X] <= val [W]

Assim, qualquer outro caminho de W será limitado pela val [X], que nunca é maior do que val [W].

Assim, a estimativa actual de val [W] é óptima e, por conseguinte, o algoritmo calcula os valores de correcção para todos os vértices.

Answer 3

Você também pode usar a "busca binária sobre a resposta" paradigma. Ou seja, fazer uma busca binária sobre os pesos, testando para cada w peso se você pode encontrar um caminho no gráfico usando apenas bordas de maior peso do que w.

A maior w para o qual você pode (encontrados através de busca binária) dá a resposta. Note que você só precisa verificar se existe um caminho, então apenas um O (| E |) em largura / profundidade-primeira busca, não um caminho mais curto. Então é O(|E|*log(max W)) em todos, comparável a O(|E|log |V|) de Kruskal / Prim Dijkstra / (e eu não posso ver imediatamente uma prova desses, também).

Answer 4

Isso pode ser resolvido usando um algoritmo estilo BFS, no entanto você precisa de duas variações:

• Em vez de marcar cada nó como "visitado", você marcá-lo com o peso mínimo ao longo do caminho que você tomou para alcançá-lo.

Por exemplo, se I e J são vizinhos, I tem um valor W1, e o peso da borda entre elas é W2, em seguida, J = min (W1, W2).

• Se você chegar a um nó marcado com valor w1, pode ser necessário observar e processá-lo novamente, se atribuir um novo valor w2 (e w2> w1). Isso é necessário para ter certeza de obter o máximo de todos os mínimos.

Por exemplo, se eu e J são vizinhos, I tem um valor w1, J tem valor w2, e o peso da aresta entre eles é w3, em seguida, se min (w2, w3)> w1 você deve observar J e processo tudo o que os vizinhos novamente.

Answer 5

Não estou certo de que Prim vai funcionar aqui. Tome este contra-exemplo:

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

Se você aplicar Prim para encontrar o caminho maxmin 1-3, a partir de 1 irá selecionar o caminho 1 --> 2 --> 3, enquanto a distância maxmin é atingido para o caminho que vai a 4.

Answer 6

Ok, respondendo a minha própria pergunta aqui apenas para tentar obter um pouco de feedback que eu tinha sobre a solução provisória eu trabalhei antes de postar aqui:

Cada nó armazena um "fragmento caminho", este é o caminho inteiro para si mesmo até agora.

0) definir vértice atual para o iniciar vértice
1) Gerar todos os fragmentos de caminho deste vértice e adicioná-los a uma fila de prioridade
2) Aqui o fragmento de fora a parte de cima da fila de prioridade, e definir o vértice corrente para o vértice terminando desse caminho
3) Se o vértice atual é o vértice alvo, em seguida, retornar o caminho
4) Goto 1 |

Eu não estou certo de que este vai encontrar o melhor caminho, porém, eu acho que a condição de saída na etapa três é um pouco ambicioso. Eu não posso pensar em uma melhor condição de saída, porém, uma vez que este algoritmo não vértices próximos (um vértice pode ser referenciado em outros tantos fragmentos caminho como ele gosta) você não pode simplesmente esperar até que todos os vértices estão fechados (como Dijkstra para exemplo)

Answer 7

Você ainda pode usar de Dijkstra!

Em vez de usar +, use o operador min ().
Além disso, você vai querer orientar a pilha / so priority_queue que as maiores coisas estão no topo.

Algo como isto deve funcionar: (i provavelmente já perdeu alguns detalhes de implementação)

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))

É garantido que sempre que você chegar a um nó que você seguiu um caminho ideal (desde que você encontrar todas as possibilidades em ordem decrescente, e você nunca pode melhorar o seu caminho através da adição de uma borda)

Os limites de tempo são as mesmas que Dijkstra -. O (Vlog (E))

EDIT: oh wait, isso é basicamente o que você postou. LOL.