Introd Flurede2014

  • Upload
    pgtime

  • View
    245

  • Download
    0

Embed Size (px)

DESCRIPTION

Introdução ao Fluxo de Redes

Citation preview

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    1

    1. INTRODUO

    Este texto contm conceitos bsicos de fluxo em redes voltado a aplicao em transportes. Pretende apresentar os modelos bsicos utilizados para solucionar alguns problemas clssicos em transportes. O texto est fortemente baseado em notas de aula ministradas pelo Prof Sang Nguyen, pesquisador renomado na rea de modelos de rede, da Universidade de Montreal. Adicionalmente o texto utiliza abordagens de Magnanti e de Bazaara, como referncias bsicas.

    Diversos tipos de problemas podem ser atacados com a abordagem de redes, entre eles: - sistemas eltricos - sistemas de comunicao - sistemas de transportes

    Na sua raiz, os modelos de rede usam uma abordagem geral, no orientada para aplicaes especficas. Neste curso ser dada a nfase a aplicaes em transportes.

    O texto apresenta conceitos bsicos e algumas provas matemticas formais, mas pode ser tomado como referncia para o aprendizado de algoritmos de resoluo dos diversos problemas.

    O captulo I mostra conceitos bsicos de grafos utilizados ao longo do curso. muito importante para unificar uma linguagem, nomenclatura e notaes que sero teis, tambm para a leitura de textos mais aprofundados na rea. O captulo II apresenta formas de representar redes em computadores. No captulo III so tratadas rvores e arborescncias timas.

    O captulo IV trata de Algoritmos de caminho mnimo. Como Sang declara so instrumentos dos mais importantes na modelagem de transportes. Embora em si, o algoritmo tenha pouca aplicao prtica, parte fundamental de algoritmos complexos de soluo de problemas de rede.

    O captulo V apresenta modelos lineares clssicos de fluxos em redes. So tratados o algoritmo de fluxo mximo e o algoritmo do fluxo de custo mnimo.

    Em geral o curso complementado com um conjunto de exerccios. Os exerccios sero resolvidos manualmente e visam dominar as tcnicas de resoluo dos diversos problemas.

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    2

    CAPTULO I CONCEITOS BSICOS EM GRAFOS

    1. CONCEITO DE CONECTIVIDADE ( CONECTIVITY)

    1.1. DEFINIES Um grafo G uma estrutura composta de um conjunto N de ns ou vrtices e um conjunto A de arcos.

    G = (N, A).

    Cada arco definido por par um ordenado de ns (i, j). Em geral denota-se por n a cardinalidade (nmero de elementos) de N e por m a cardinalidade de A.

    n=|N| e m=|A|

    Representao grfica: Em geral se representa o grafo por um conjunto de crculos ou retngulos representando os ns e um conjunto de linhas com ou sem setas, ligando alguns pares de ns e representando, desta forma, os arcos.

    Figura 1: Representao de um grafo.

    No caso do grafo da figura 1, o conjunto de ns N = {1, 2, 3, 4, 5, 6}.

    Pode-se representar a conexo entre ns, sem se preocupar com a direo dos arcos. Neste caso tem-se um grafo no direcionado. comum definir arcos no direcionados como um conjunto G = (N, E), onde E representa o conjunto de arestas, denominao especfica para designar arcos no direcionados.

    Aos arcos e ns podem ser associados valores. Um grafo, com arcos valorados, define uma rede. Portanto uma Rede um grafo com valores numricos relacionados arcos e ns. A valorao dos arcos pode-se referir a comprimentos, ou tempos de viagem, ou ainda capacidade de arcos, ou a custos, ou capacidades de usar um n.

    1 2

    3

    4 5 6

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    3

    1.2. DEFINIES PRINCIPAIS

    Seja G = (N, A). Arco a A a = (i, j). i : cauda (tail) do arco a j: cabea (head) do arco a

    Adjacncia: Os ns i e j so adjacentes. Eles esto conectados por um arco.

    Dois arcos so adjacentes se eles tem um n comum (pelo menos)

    Arcos: (i, j) e (k, j) so adjacentes.

    Grau de um N: O grau do n definido como o numero de arcos incidentes ao n. Um arco incidente ao n se o n i cauda ou cabea do arco

    Semi-grau interior (indegree of a node)

    O semigrau interior designado por d - (i) o nmero de arcos incidentes para o n, ou seja, o n i cabea dos arcos. Os ns, que so as caudas dos arcos incidentes a i forma o conjunto de precedentes, ou predecessores de i, denotado por: -(i).

    Semi-grau exterior (Outdegre), designado por d+ (i) o nmero de arcos incidentes desde o n i, ou seja o n i cauda dos arcos. Os ns que so as cabeas dos arcos inicidentes desde i, formam o conjunto de sucessores de i denotado por: +(i).

    N grafo da figura 2 abaixo, o n i tem outdegre = 2 e grau = 5 ( 2+3).

    i

    Figura 2: Grau de um n.

    Lao (Loop) Um lao (loop) ocorre quando o n inicial (a cauda) e o n final (a cabea) do arco coincidem.

    Loop (lao): arco (i, i) da figura 3

    i j

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    4

    Arcos Paralelos Arcos paralelos ocorrem quando dois ou mais arcos tem os mesmos ns iniciais e finais.

    i

    Figura 3: Lao e arcos paralelos. Grafos Simples: So grafos sem loops e sem arcos paralelos e com no mximo 1 (0, ou 1) arco entre qualquer par de ns.

    2. PROPRIEDADES DE CONECTIVIDADE

    Este item trata de conceitos relativos a cadeias, caminhos etc., que so a base do conceito de conectividade do grafo.

    Seja o grafo G = (N, A)

    CADEIA: Uma Cadeia L de ordem q uma seqncia L = {a1, a2,..., aq - 1, aq} de q arcos, tais que para qualquer k com 2 k q - 1, o arco ak tem um ponto comum tanto com o arco precedente (ak - 1), como com o arco seguinte (ak + 1).

    OBSERVAO: A cadeia no leva em considerao a orientao dos arcos.

    L = {(2, 3), (2, 1), (1,4),} Linha pontilhada da figura 4

    Figura 4: Cadeia.

    CADEIA ELEMENTAR Uma cadeia elementar se ela atravessa cada vrtice, no mximo uma vez. A cadeia L da figura 4, no elementar. A cadeia {(2,3), (3,4), (4,1)} elementar.

    1 4

    2 3

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    5

    N i do arco a1 que no adjacente a a2 e o n j de aq, no adjacente a aq - 1 so os pontos extremos da cadeia.

    Diz-se tambm que L cadeia (i- j)

    L cadeia aberta se i j

    CICLO Se i = j ento L cadeia fechada , que se denomina de Ciclo.

    CAMINHO Caminho Cadeia em que todos os arcos so orientados no mesmo sentido. importante diferenciar cadeia de caminho, considerando a orientao dos arcos. p = {a1, a2, a3, ..., aq} a1 = {i0, i1} a2 = {i1, i2} e aq {iq - 1 , iq}

    Um caminho elementar se no atravessa nenhum n mais de uma vez.

    CIRCUITO Se o Caminho fechado tem-se um circuito. O circuito , portanto, um ciclo onde todos os arcos esto orientados no mesmo sentido.

    Pode-se ter ciclos e circuitos elementares segundo os conceitos anteriores. O fato de chegar ao n inicial no significa atravessar o n inicial.

    Se h cadeia conectando i e j; i e j so conectados. Portanto o conceito de conectividade de grafos est associado presena de cadeias e no de caminhos.

    Por outro lado se diz que um n j acessvel desde um n i se existe um caminho (i-j). Repara-se a diferena entre o conceito de conectividade associado a cadeias e de acessibilidade associada a caminhos.

    Um grafo sem ciclos um grafo acclico.

    GRAFO COMPLETO Um grafo dito completo se satisfaz as condies:

    Se (i, j) A (j, i) A,

    Ou seja, os ns i e j so ligados pelo menos por 1 arco

    SUBGRAFO Um subgrafo G = (N, A) de G = (N, A) um grafo gerado por um subconjunto de ns N N. um grafo tendo N como conjunto de ns e A conjunto de arcos de A com

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    6

    os 2 extremos em N. Para se obter um Subgrafo apagam-se alguns ns e os arcos incidentes a estes ns.

    1 2

    4 3

    2

    3

    Figura 5: Grafo e subgrafo (apagam-se ns e seus arcos)

    GRAFO PARCIAL: Um Grafo parcial G = (N, A) de G um grafo com:

    - N como conjunto de ns - A como conjunto de arcos

    Ou seja, G gerado por A, um subconjunto do conjunto de arcos A. Esta a nica diferena.

    1 2

    4 3

    Figura 6: Grafo parcial. (apagam-se arcos)

    COMPONENTE DE UM GRAFO Um Componente do grafo G um mximo subgrafo aonde todos os pares de ns so conectados, ou seja, um componente no subgrafo de nenhum outro componente de G.

    Figura 7: Componentes de um grafo. G tem 2 componentes A e B

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    7

    GRAFO CONECTADO Um grafo que s tem 1 componente um grafo conectado.

    GRAFO FORTEMENTE CONECTADO Um grafo fortemente conectado se para cada par de ns i e j, j acessvel desde i e i acessvel desde j.

    COMPONENTE FORTE DE UM GRAFO Um componente forte de um grafo (CF) um mximo subgrafo fortemente conectado de G. Isto ele no um subgrafo de nenhum outro subgrafo fortemente conectado de G. (Figura 8)

    GRAFO ANTISIMTRICO Um Grafo antissimtrico (assimtrico) se atende a condio:

    Se (i, j) A ento (j, i) A

    GRAFO BIPARTITE Um grafo Bipartite aquele onde:

    o conjunto de ns N pode ser partido da forma: N = {S T}, com S T =

    1. CF

    2. CF

    3. CF

    4. CF

    Se tem i j No tem

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    8

    e onde nenhum par de ns em S, nem em T adjacente.

    Figura 9: Grafo bipartite

    3. RVORE E ARBORESCNCIAS

    Este item apresenta outras estruturas especiais e importantes de grafos que so rvores (Trees) e arborescncias (arborescences).

    Um grafo uma rvore se conectado e no contem nenhum ciclo ( acclico).

    1 2

    3 4

    Figura 10: rvore

    RVORE Seja o grafo G = (N, A) e n a cardinalidade de |N|. Duas quaisquer das trs propriedades definem uma rvore e implica na terceira.

    1) G conectado 2) G tem exatamente (n-1) arcos 3) G no contm nenhum ciclo (acclico)

    Se 1 e 3, so verdadeiros, ento 2 verdadeiro.

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    9

    Se 1 e 2 3

    Se 2 e 3 1

    RVORE EXTENDIDA (spaning tree) Um rvore extendida ST (Spanning Tree) do grafo G = (N, A) um grafo parcial de G que tambm uma rvore, ou seja, contm todos os ns de G e um subconjunto de arcos de G.

    A linha tracejada uma spanning tree de G ?

    1 2 5

    3 4 6

    Figura 11: rvore extendida ST(Spanning tree)

    EXEMPLO: Com o componente (N={5,6}, A= (5,6)) o grafo acima no permite uma rvore extendida (spanning tree), mas no grafo G com N={1,2,3,4} a linha tracejada uma ST.

    Proposio 1: G contm uma ST (spanning tree) se somente se G conectado

    Se ao grafo parcial da ST se agrega um arco qualquer de G, fora da ST, forma-se um ciclo.

    Proposio 2: Cada arco fora da ST define um nico ciclo com os arcos da ST.

    ARBORESCNCIA: Uma arborescncia pode ser enraizada (rooted) de (para) um n i. Neste caso i chamado raiz da arborescncia. Repare-se que para o conceito de rvore no se leva em considerao a orientao dos arcos, ao contrrio do que ocorre com a arborescncia.

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    10

    k

    i j

    n

    l

    s

    Figura 12: Arborescncia enraizada de i

    Figura 13: Arborescncia enraizada para o n i

    Todos os arcos so orientados para ou desde o n i

    Arborescncia enraizada de i uma rvore tal que o semigrau interior (indgree) do n i zero e para cada outro n exatamente 1.

    Portanto a rvore de rota mnima arborescncia. Em geral toda arborescncia uma rvore, mas nem toda rvore uma arborescncia. Pode-se buscar a rota mnima (RM) de 1 n para todos os outros, o que cai no caso (1), arborescncia desde o n i, ou a RM de todos os ns para 1, o que seria o caso (2), arborescncia para o n i.

    Se, em uma arborescncia, h um caminho (i-j) de i para j, ento i um ancestral de j e j descendente de i. Um vrtice sem descendentes uma folha. Um n i e todos os seus descendentes formam uma arborescncia enraizada em i.

    No caso de rvores observa-se a seguinte propriedade. Uma rvore tem n ns e n-1 arcos. Portanto o grau total de todos os ns duas vezes o nmero de arcos (cada arco gerando dois graus), ou seja, 2*(n-1) a ser dividido entre n ns. Como todos os ns tem pelo menos o grau 1 (esto conectados), tem-se pelo menos 2 ns de grau 1 em uma rvore. Os ns de grau 1 na rvore so denominados de ns pendentes.

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    11

    CAPTULO II REPRESENTAO DE GRAFOS EM COMPUTADORES

    1. INTRODUO

    A implementao de algoritmos de fluxos em rede em computadores exige uma estruturao especial dos dados de rede de forma a ser possvel acessar eficientemente os elementos necessrios a cada algoritmo. Alm do mais, pelo menos uma das representaes de grafos em matrizes tem um importante significado matemtico para a soluo de certos problemas de otimizao.

    Neste captulo apresentaremos as estruturas em forma de matriz de incidncia e listas de arcos adjacentes

    2. MATRIZES DE INCIDNCIA

    Existem dois tipos mais importantes de matrizes de incidncia. A matriz de incidncia n-n e a matriz de incidncia n-arco.

    2.1. MATRIZES DE INCIDNCIA N-N

    A Matriz de Incidncia n - n tambm chamada de matriz de adjacncia.

    Dado o conjunto de arcos A = (ai j), forma-se uma matriz quadrada de tamanho n igual a |N|, cardinalidade do conjunto N de ns. Os elementos aij da matriz representam a adjacncia entre o n da linha i e o n da coluna j. Assim tem-se:

    ai j [0, 1] e

    ai j =

    senojiarcohase ),(1

    Por exemplo:

    Figura 2.1. Exemplo de grafo

    A matriz de adjacncia que representa tal grafo dada a seguir.

    1 3

    2 4

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    12

    n 1 2 3 4 1 0 1 1 0 2 1 0 1 1 3 0 1 0 1 4 0 0 1 0

    Tomando uma linha i da matriz, o nmero de elementos 0 d o nmero de arcos incidentes desde o n i (grau exterior de i):

    d+ (i) = j

    ai j

    Tomando-se um elemento j da coluna a soma de elementos da coluna d o nmero de arcos incidentes para o n j (grau interior de j).

    d-(j)= i

    aij

    A memria necessria para armazenar a matriz proporcional a n2

    2.2. MATRIZES DE INCIDNCIA N-ARCO

    A matriz de incidncia n-arco relaciona os ns associados s linhas da matriz, com os arcos, associados s colunas da matriz.

    A = (ai j) com valores 0, +1, -1

    As linhas correspondem a n ns e as colunas a m arcos

    A = (n X m)

    Cada elemento aij da matriz poder assumir os valores:

    ai j +

    11

    se arco j incidente do n i exteriormentese arco j incidente para o n i eriormenteseno

    ( ) ( )( ) (int )

    Para o grafo da figura 2.1 a matriz de incidncia n-arco dada a seguir.

    N/arco (1, 2) 1

    (1, 3) 2

    (2, 1) 3

    (2,3) 4

    (2, 4) 5

    (3, 2) 6

    (3, 4) 7

    (4, 3) 8

    1 +1 +1 -1 0 0 0 0 0 2 -1 0 +1 +1 +1 -1 0 0 3 0 -1 0 -1 0 +1 +1 -1 4 0 0 0 0 -1 0 -1 +1

    Portanto, as colunas tem dois elementos diferente de 0 um +1 e um -1.

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    13

    A memria necessria para armazenar esta matriz proporcional a n X m. No caso mais geral m n2, logo a memria n3

    A matriz de incidncia n-arco tem a propriedade de ser totalmente unimodular. O determinante de qualquer submatriz no singular igual a +1 ou -1. Se uma submatriz obtida de A, eliminando uma linha arbitrria de A, cumpre-se que os pontos extremos de .x = b tero valores inteiros para qualquer vetor inteiro b.

    Assim, em geral, problemas lineares de fluxos em rede tm soluo inteira.

    Para uma matriz esparsa, com muitos zeros, ou seja: m

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    14

    O vetor guarda apenas o n de destino (cabea) de cada arco.

    ndice 1 2 3 4 5 6 7 8

    2 3 1 3 4 2 4 3

    Em geral para se acessar os arcos com cauda em i percorre-se o vetor desde (i) a (i+1)-1. Para tratar o ltimo n define-se (n+1) = m+1, sendo n, nmero de ns e m o nmero de arcos da rede.

    Os arcos com cauda no n 3 se encontram entre o ndice (3)= 6 a (4)-1=8-1=7, na lista . Ou seja, (6)=2 , (7)=4. Os arcos so (3,2) e (3,4).

    No caso de guardar os predecessores, esta estrutura faz uso de dois vetores e ( ), de dimenso (n + 1) (nmero de ns + 1) e ( ) de lista de ns predecessores de um n i, de dimenso m (nmero de arcos) comeando de (i). Um n predecessor um n adjacente a um n i ligado por um arco, cuja cabea i. Como a um n i pode haver vrios arcos cuja cabea i, pode haver mais de um predecessor de i.

    Para os ns predecessores as listas so construdas da seguinte forma: os arcos so ordenados agora pelos ns de destino (cabea) dos arcos.

    ndice i j 1 2 1 2 1 2 3 3 2 4 1 3 5 2 3 6 4 3 7 2 4 8 3 4

    A lista (i) indica o ndice do primeiro arco cuja cabea i.

    1 2 3 4 5 1 2 4 7 9

    (k) guarda o n de origem (cauda) do arco k. Tambm se pode dizer que a lista de ns predecessores de i.

    1 2 3 4 5 6 7 8 ndice 2 1 3 1 2 4 2 3

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    15

    Por exemplo, ainda considerando a figura 2.1. Os ns predecessores de 3 esto em (3)=4 (4)-1=7-1=6, ou seja, (4)=1 ; (5)=2 ; (6)=4, indicando a existncia dos arcos (1,3),(2,3) e (4,3).

    Dependendo da utilizao do problema faz-se uso de e/ou .

    Ento quando o problema exige trabalhar com ns sucessores usa-se e . Para trabalhar com ns predecessores usa-se e .

    A lista de arcos exige um uso de memria: 2 (n + 1) + 2m ou (n + 1) + m, dependendo se usa-se uma ou ambas as estruturas. uma das estruturas mais usadas em implementao de modelos de rede.

    4. MTODOS DE BUSCA EM REDE

    Alguns problemas exigem que se visite todos os ns de um grafo em uma certa ordem. Os mtodos bsicos de visita so o breadth-first search (busca em amplitude ) e o depth-first-search (busca em profundidade).

    4.1. BUSCA EM AMPLITUDE (BREADTH-FIRST SEARCH)

    Para esta busca, partindo-se de um n qualquer i0, visita-se os sucessores de i0 (i1, i2,...,ik) em qualquer ordem. Depois de terminar com os sucessores de i0, repete-se a busca desde i1 (o primeiro sucessor de i0) visitando todos os ns sucessores de i1, ainda no visitados. Depois toma-se os sucessores no visitados de i2 e assim sucessivamente, at visitar todos os ns do grafo.

    Figura 2.2.: Busca em amplitude. (A linha pontilhada indica a arborescncia associada busca).

    Para a figura 2.2, partindo-se do n 3 como i0, os ns visitados so 3, 1, 4, 5, 2, 6.

    De 3 visita-se os sucessores 1, 4 e 5. De 1, como 3 j foi visitado, visita-se 2. De 4 visita-se 6, j que 3 e 5 j foram visitados.

    2 4

    1 6

    3 5

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    16

    Observa-se que a ordem de visita no nica. Se se marca os arcos usados na busca, forma-se uma arborescncia enraizada em i0 (o grafo conectado e no contm nenhum ciclo, j que cada n s visitado uma vez. O grau interior de i0 0 e 1 para todos os outros ns).

    Define-se Pk(i0) o conjunto de ns acessvel desde i0, por um caminho de ordem k. Um caminho de ordem k um caminho com k arcos. Em um BFS os ns so visitados na ordem:

    i0, P1(i0), P2(i0), ...

    4.2. BUSCA EM PROFUNDIDADE (DEPTH-FIRST SEARCH)

    Na DFS parte-se de um n arbitrrio i0 e segue-se um arco (i0, i1) para o n i1, depois visita-se o arco ( i1,i2) para i2. Ou seja, a partir de um n i, visita-se sempre um n sucessor j ainda no visitado, usando o arco (i, j). Depois repete-se a partir do n j para um n k. Se o n k j foi visitado volta-se para o n j e busca-se outro sucessor de j ainda no visitado. Se todos os ns sucessores de j j tiverem sido visitados retorna-se ao n i (backtracking) e buscam-se outros ns sucessores de i ainda no visitados.

    Para o grafo da figura 2.2 partindo-se do n 3 visitam-se: 3, 1, 2, 4, 5, 6.

    Do n 3 vai-se ao n 1. De 1 para o n 2. De 2 a 4. De 4 a 5. De 5 no se pode seguir. Volta-se para 4 e visita-se 6.

    Com esta busca forma-se a arborescncia da figura 2.3.

    Figura 2.3. Arborescncia resultante da busca em profundidade (DFS)

    2 4

    Backtracking. 1 6

    3 5

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    17

    5. COMPLEXIDADE DE ALGORITMOS

    Estimar o nmero de computaes elementares Somax

    comparacao etc

    ,

    ,

    em funo de uma

    medida do tamanho do problema equivale a determinar a complexidade computacional do algoritmo.

    Seja n uma medida do tamanho de problema, por exemplo, o nmero de ns na rede. Pode-se dizer que a complexidade do algoritmo de ordem n, ou O (n), se o nmero de operaes C1* n + C2 , sendo C1 e C2 constantes positivas para qualquer n.

    Um algoritmo de 0 (n2) tem nmero operaes: C1*n2 + C2 *n.

    Se a ordem 0 (lg2 n) o nmero de operaes: C1 lg2 n + C2

    As constantes podem influenciar, mas para problemas com muitas variveis, ou seja, n grande, vale em geral na prtica: 0 (nk) < 0 (nK + 1)

    EXEMPLO: O nmero esperado de operaes para um nmero de variveis igual a 10, em algoritmos com diversas complexidades dado abaixo.

    n = 10 lg2 n n

    3.3 10

    n lg n n

    2

    33 100

    2n 210 = 1024 n! 30 000 000

    Pode-se trabalhar com a complexidade esperada ou com complexidade no pior caso, mas preciso ter cuidado com anlise do pior caso, por exemplo:

    O Simplex tem 0 nn m

    !( )

    , mas trabalha na prtica, de forma muito eficiente.

    Para maiores informaes, pode-se se remeter a Lawlev, E.L. (76) Introduction to the Complexity of Algorithms. Aplyed Computation Theory: Analysing design, modelling. Prentice-Hall.

    O que interessa da complexidade que o nmero de operaes ser proporcional ao tempo consumido na mquina. Se algoritmo tem complexidade O(n2) o tempo de CPU ser proporcional a n2. Ao desenvolver um algoritmo a anlise da complexidade d uma idia da eficincia do algoritmo, quando comparado com a complexidade de outro algoritmo que resolve o mesmo problema.

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    18

    CAPTULO III RVORES E ARBORESCNCIAS TIMAS

    1. PROBLEMA DA RVORE GERADORA MNIMA (MINIMUM SPANNING TREE MST)

    Achar a rvore de extenso mnima um dos problemas de maior aplicao em fluxos em redes. Certos problemas aplicados a logstica, fazem tambm uso da MST. O problema definido como se segue:

    Seja G = (N, E) um grafo no dirigido e conectado. Para cada aresta e E e = (i, j) se associa valor wi j (we).

    O peso de ST w () = e T

    we , Sendo = (N, T) uma S.T (spanning tree) de G

    O Problema de MST consiste em determinar a ST com peso mnimo.

    MST pode ser definida como:

    rvore estendida tal que W (*) = min .

    ew

    Um exemplo de aplicao de MST conectar n cidades por rede de caminhos, com um custo mnimo de construo. Para cada par de cidades (i, j): tem-se: wi j , custo de construir estrada de i para j.

    No grafo da figura 3.1 os ns correspondem a cidades e as arestas a caminhos alternativos

    Figura 3.1: rvore estendida em G

    No grafo mostrada uma tentativa de rvore estendida com as arestas pontilhadas. Qual a condio para que ST seja mnimo? Isto ser mostrado a seguir.

    i wik k

    e1 e

    e2 e3

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    19

    Coloca-se uma aresta qualquer e na ST formando um ciclo e deixando, portanto, de ser uma rvore. Retirando-se outra aresta, por exemplo e2 , o grafo parcial permanece uma ST.

    Seja que se cumpre we1 < we2. Tem-se uma nova ST , com w () < w(), pois we1 < we2.

    Figura 3.2 Nova rvore estendida, pela substituio de e2 por e

    Lembra-se que e era a aresta fora da rvore original. Com a incluso de e na MST forma-se (e) que um ciclo nico formado por algumas arestas do T e e, como mostrado na figura 3.3. Este ciclo formado pela incluso de uma aresta qualquer fora de T a uma ST chamado de ciclo fundamental.

    e'

    Figura 3.3. Ciclo fundamental formado pela incluso de e na ST

    A anlise deste ciclo ilustra a condio C1 necessria para uma MST.

    C1. (N1T) uma M.S.T. se e somente se, para qualquer aresta (seja e) no pertencente rvore (T), o peso de e cumpre: we we para todas as arestas do ciclo fundamental definido pelas arestas de mais a aresta e

    we we e (e)

    (e) o ciclo fundamental formado pela incluso de e.

    evidente que se w(e) < w(e) de alguma aresta do ciclo fundamental, a substituio de e por e conduziria a uma ST de menor peso que a original, o que seria uma contradio com a hiptese dela ser uma MST.

    A condio necessria suficiente.

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    20

    2. ALGOITMO DE KRUSKAL (1956)

    O algoritmo de Kruskal, baseado no teorema anterior (C1), constri a MST de uma rede qualquer. Inicialmente as arestas so ordenadas em ordem no decrescentes:

    wei we2 we3 ......

    Em seguida, o algoritmo toma e vai incluindo na rvore, as (n - 1) primeiras arestas que no formam um ciclo com as j existentes na rvore, sendo n o nmero de ns do grafo.

    Figura 3.4. Construo de MST por Kruskal. Exemplo: e11,2: aresta e11 , pso : 2

    Ordenando-se as arestas do grafo da figura 3, tem-se:

    e1 e11 e9 e2 e10 e3 e7 e5 e6 e8 e4

    1 2 3 4 4 5 5 6 7 9 10

    n= 6 ns.

    O objetivo tomar as primeiras n-1 (5) arestas que no formam ciclo, com as outras j escolhidas na rvore.

    Inicialmente toma-se e1 , e11 , e9 e e2 , que no forma ciclo.

    e10 forma ciclo com e11 e e9 (Fica de fora)

    e3 forma ciclo com e9 e e2 . e7 forma ciclo com e1 , e9 e e2

    e5

    Com esta ltima, tem-se 5 arestas formando a MST.

    e1,1 e2,4 e3,5 e5,6 e6,7

    e4,10

    e7,5

    e8,9 e9,3 e11,2

    e10,4

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    21

    Figura 3.4: rvore resultante do algoritmo de Kruskal

    3. ALGORITMO DE PRIM

    Teorema 2: Seja e uma aresta com peso mnimo entre todas as arestas. Incidente a um n i. Ento e est contido em *.

    Prova: Seja * uma MST e -(i), o conjunto de arestas incidentes a i. Neste conjunto est e, que a aresta de menor peso do conjunto, mas no pertence a *.

    Figura 3.4 : Ciclo fundamental com e.

    A aresta e forma um ciclo fundamental com outras arestas de *. . Se* MST os pesos das outras arestas devem ser menores ou iguais a e ou:

    we wu u * (e)

    O ciclo fundamental contm uma aresta e (e -(i)), mas e e. Por hiptese w(e) w(e).

    Logo, para atender as duas condies: we = w

    Trocando-se por e tem-se novo MST, * com mesmo peso da anterior.

    Logo e deve pertencer a um MST *.

    e1 e2 e5

    e9 e11

    i

    e e

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    22

    Corolrio 1 (generalizao) Se um subconjunto de arestas formando uma sub-rvore S conhecida como parte de uma MST, ento existe uma MST, que contm S e uma aresta de menor peso conectando S para os ns restantes do grafo.

    Este corolrio uma generalizao do teorema 2, substituindo o n i pelo conjunto de ns S.

    O algoritmo de PRIM baseado no teorema 2.

    Comea com i0 e escolhe aresta de peso mnimo, incidente a i0. Essa aresta parte da MST. Esta aresta pode ser considerada como a sub-rvore S. Das arestas que partem (incidem sobre) dos ns da sub-rvore S, torna-se a aresta de menor peso. Pode-se prosseguir at formar a MST.

    Para implementar o algoritmo a cada n j, associa-se 2 etiquetas: [pij , j]

    pij = wij peso da aresta (j , j)

    j = n precedente ao n j. Os pesos das arestas no existentes so colocados como um valor muito alto ;wij = para (i,j) E

    Algoritmo de PRIM O grafo conectado G=(N,E) dado pela lista de adjacncia -(.).

    Passo (P0): Escolha um n arbitrrio, seja i0

    pii0 = 0 ; i0 = -1

    pij = wij , j = i0 para j i0

    Lembrar que se (i, j) E, wi j = +

    P = {i0} , T = , X = N -{i0}

    Sendo: - P = subrvore S. - T = rvore total - X = ns restantes

    Passo 1 (P1): Adio de uma aresta subrvore atual.

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    23

    Encontrar k tal que pik = min piJj X

    Fazer P P {k} T T {k, k} X X - {k}

    Se | X | = pare. T conjunto de arestas do MST

    Passo 2 (P2): Reviso de etiquetas

    Para todo j X (ns fora da subrvore)

    Se pij > wk j

    Ento pij = wk j , j = k

    Volta para o passo 1.

    Pode-se expressar o algoritmo em trs passos:

    a) Iniciar com qualquer n i: Determinar o arco com extenso mnima (incidente a i). Incluir arco na rvore (seja arco i, j): n j entra na rvore.

    b) Se todos os ns j esto na rvore termine. Seno v para c.

    c) Entre todos os ns presentes na rvore atual, busque um arco (i,j) incidente com extenso mnima, cujo n j, adjacente ainda no est na rvore. Incorporar o arco e o n adjacente rvore e voltar para b.

    Figura 3.5. Grafo para o exemplo do algoritmo de PRIM

    Para o grafo da figura 3.5 a soluo passo a passo :

    7 5 3 9 10

    1

    2

    7 6 8 4

    2

    1

    2

    3

    4

    5

    6

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    24

    (P0) Seja i0 = {4} = P T = X = (1, 2, 3, 5, 6) Valor mnimo na etiqueta [2,4] do n 2. k=2.

    (P1) T = {(4, 2)} P = {4, 2} X = N P

    (P2) Ver n 3 etiqueta [4, 6]. 6 < 7 no muda N 1 [ 4, 3] 3 < 7 Volta P 1

    (P1) A menor etiqueta [3,4] do n 1. k=1. T = {(4, 2), (4, 1)} P = {4, 2, 1} X = N - P

    (P2) Agora de 1 n 3 [6,4] 6 > 5 muda para [5,1] n 6 [9,4] 9 > 1 muda [1, 1]

    (P1) menor etiqueta [1,1]. Entra n 6

    T = T U {(1, 6)} P = P U {(6)} X = N - P

    (P2) do n 6 : no muda nada

    (P1) O menor label [4,4] do n 5. Entra o n 5

    (P2) Muda label de 3 para [2,5] e completa a MST

    Existe um problema especial de MST denominado de Problema de Steiner. Trata-se de encontrar uma rvore mnima que se estende sobre um subconjunto de fixo de ns do grafo. Tal rvore mnima conhecida como rvore de Steiner e pode conter outros ns alm do conjunto fixo. Os ns do conjunto a ser estendido so chamados de ns de Steiner.

    1 2 3 4 5 6 [3,4] [2,4] [6,4] [0,0] [4,4] [9,4] [ 5,1] [1, 1] [2,5]

    Valores das etiquetas no ns.

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    25

    Busca do menor valor O passo 1 do algoritmo de PRIM busca o menor valor de etiqueta para todos os ns. Essa busca exige comparaes entre todos os ns de fora da rvore. Como esse passo repetido n-1 vezes, interessante buscar uma estrutura para reduzir o nmero de comparaes. Uma estrutura muito usada a estrutura de heap.

    O heap uma rvore binria de tal forma que o melhor valor se encontra sempre no topo da rvore e os elementos em cada nvel tm sempre de valor pior que o valor do elemento imediatamente superior.

    Para qualquer elemento da rvore vale:

    Valor (i) < valor (2i) < valor (2i+1).

    No caso de busca de menor valor, o melhor significa o menor.

    1 i

    2i 2i+12 3

    4 5 6 7

    Figura 3.6: Estrutura de heap

    Nesta estrutura as comparaes so feitas s de um lado da rvore em um caminho linear entre a folha e a raiz da rvore.

    Ex.: Ns { 1, 2, 3, 4, 5, 6, 7, 8 } Valor{10, 5, 8, 5, 12, 17, 3, 9}

    1 106 6 17

    ValorN

    2

    4 5

    5

    33 8

    8 9

    7

    Figura 3.7: Ordenao de valores na estrutura do heap

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    26

    CAPTULO IV MODELOS DE CAMINHOS MNIMOS

    1. INTRODUO

    dado o grafo G = (N, A) (i, j) A e a cada arco (i,j) se associa di j , o comprimento do arco (i, j). di j pode ser positivo ou negativo.

    Seja : Comprimento do caminho p = i ji j p

    d( , )

    Os modelos de caminho mnimo resolvem o problema de encontrar o caminho com comprimento mnimo (Rota Mnima RM). Este o problema mais fundamental dos problemas de rede. um modelo com uma aplicabilidade muito grande, pois o clculo de rota mnima muito usado como sub-rotina em muitos algoritmos para solucionar problemas complexos em redes.

    H algumas observaes a destacar:

    1) Clculo do RM entre 1 par de pontos no mais simples que clculo de RM entre 1 ponto e todos os outros. Os problemas tm mesma ordem de dificuldade.

    2) H diferenas entre clculo da RM para redes arcos com di j > 0 i j e redes com arcos de comprimento positivo e negativo (di

    j < 0 e di j > 0). Em geral se sabe que as complexidades so:

    Para di j > 0 0 (n2)

    di j > 0 e < 0 0 (n3)

    3) No h algoritmos eficientes para calcular RM em redes com circuitos negativos. Dreyfeus (1969).

    2. EQUAES DE BELLMAN

    As equaes propostas por Bellman so uma forma de resolver o problema da rota mnima atravs da programao dinmica.

    Define-se:

    di j = comprimento de (i, j) se o arco (i,j) existe, seno di j =

    pii : comprimento da rota mnima de um n inicial (seja 1) ao n i

    Supe-se que a rede no tem circuitos negativos.

    No incio se tem: pi1 = 0 para j 1

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    27

    Seja (k, j) o ltimo arco na rota mnima de 1 a j.

    Figura 4 .1: Princpio de otimalidade de Bellman.

    Segundo Bellman o subconjunto de 1 - k (caminho de 1-k) deve ser tambm rota mnima para valer pij = pik + dk j (Principio de otimalidade).

    pi1 =

    pij = Mnimo pii + di j para todo j 1

    i j

    Teorema 1: Se a rede no contm circuitos no positivos, ento h uma soluo nica finita para a equao de Bellman, onde pij o comprimento da RM entre 1 e j.

    A Soluo das equaes muito complicada. O Algoritmo no trivial e a Soluo s simples se no h ciclos.

    3. REDES COM COMPRIMENTOS DE ARCOS POSITIVOS (DJKSTRA)

    O algoritmo de DJKSTRA (1956) resolve de forma eficiente o problema de RM para redes com arcos no negativos. Em termos gerais, o mtodo trabalha da seguinte forma.

    H ns com etiqueta permanente, que so aqueles que no podem ser melhorados. Ou seja, j se encontrou a rota mnima entre a origem e o n. E h ns com etiqueta temporria. So os ns que ainda podem ser melhorados. Ou seja, pode-se encontrar um outro caminho da origem at o n, melhor do que o caminho atual.

    A cada etapa o algoritmo seleciona um n k para ser permanente. No incio o n de origem. A partir da, ser sempre um n com a menor etiqueta temporria.

    Uma vez que este n tornado permanente, tenta-se melhorar a etiqueta dos ns da rede. Os nicos ns que podem ser melhorados so somente os ns j temporrios, que so ligados com um arco (k, j) desde o n recentemente tornado permanente.

    Faz-se ento uma varredura, a partir do n k aos ns j temporrios adjacentes a ele. Se o custo do caminho atual at cada n j, for maior que o custo do caminho desde a origem at k mais o custo do arco (k,j), ento pode-se melhorar a etiqueta do n j e o n precedente ao n j passa ser o n k (figura 4.2).

    No exemplo da figura os ns j, l e m esto ligados por arcos desde o n k. O n j tem um custo atual da origem at ele de 50. O custo de um novo caminho passando pelo n

    1 k j Subconjunto de 1-k arco (k,j)

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    28

    k, com custo 35, mais o custo no arco (k, j) de 10 d um total de 45, que menor que 50. Assim o novo caminho at j ter um custo de 45 e o novo n precedente de j o n k. A etiqueta de j muda para [45,k].

    1515

    10l

    jj

    km

    [35, a]

    [50, b]

    [50, k]

    [60, c]

    k

    Caminho a m Novo caminho at j

    Etiqueta [pi, ] : custo do caminho e n precedente. Figura 4.2: Varredura aos ns j,l e m a partir do n k

    Formalmente o algoritmo de caminho mnimo de Djkstra apresentado a seguir:

    O mtodo define para cada N i:

    Um par de etiquetas (pii , i ), sendo:

    pii : Valor da rota atual da origem a i

    i : N precedente na rota atual da origem a i.

    Define tambm dois conjuntos de ns:

    P : Conjunto de ns permanentes. So os ns para os quais j foi encontrado o caminho mnimo desde a origem.

    T : Conjunto de ns Temporrios. So os ns cujos valores de etiquetas ainda podem mudar.

    O Algoritmo de Dijkstra descrito a seguir.

    Passo 0 : Inicializao. Seja a o n inicial. Definem-se os valores:

    pia = 0 ; a = -1 pij= daj ja ; a = 0

    Se (a,j) A daj =

    Textualmente: O n inicial a recebe as etiquetas (0, -1). Os demais ns j recebem o valor (daj,0), sendo daj o valor do arco que liga a ao n j. Se no existir o arco, daj = .

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    29

    P a T = j / j ={N-a}

    Textualmente: O n a permanente, est no conjunto de permanentes, os demais ns so temporrios.

    Passo 1: Encontrar o n k tal que pik = min pij

    jT

    Textualmente: Entre todos os ns temporrios, escolha aquele (que chamamos de n k) com menor etiqueta de valor da rota, pi.

    Conj. P P U k ; T T - k . Se T = 0 Pare: os pij so custos da RM

    Textualmente: Retire o n k no conjunto de temporrios e o coloque no conjunto de permanentes. Se o conjunto de temporrios ficou vazio, o algoritmo terminou.

    Passo 2: Reviso de etiquetas

    j T faa e tal que o arco (k,j) A:

    Se pij > pik + dkj , ento

    Incio

    pij = pik + dkj ,

    j = k

    Fim, ento volte para 1.

    Textualmente: Entre todos os ns j temporrios, acessveis por um arco desde o n k, verifique se o valor do caminho atual maior que o valor do caminho passando pelo n k e pelo arco de acesso a j. Se o novo caminho tem um valor menor troque as etiquetas. pij = pik + dkj e k passa a ser o novo predecessor de j. Feito isto para todos os ns acessveis desde o n k, volte para o passo 1.

    Figura 4.3: Exemplo de etiquetagem inicial para um caminho mnimo a partir do n 1.

    5

    1

    2 4 6

    2

    7

    6 8

    4 5 5

    1 3

    2 4

    6

    5 [2,1]

    [5,1]

    [4,1] [,0]

    [,0] [0,-1]

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    30

    No exemplo da figura 4.3 deseja-se encontrar a rota mnima desde o n 1 at todos os outros. J dado o passo zero, inicial do algoritmo. S o n 1 permanente, os demais so temporrios. No passo 1 se identifica o n com menor etiqueta entre os temporrios. Trata-se do n 2 com valor 2. esse o n k, a partir do qual se faz a varredura at os ns temporrios adjacentes tentando mudar a etiqueta. Os ns j temporrios adjacentes so:

    n 3 com etiqueta [4,1] n 4 com etiqueta [4,1].

    O arco (2,3} tem custo 1. Assim o custo de chegar a 3 via o n 2 : O custo at o n 2, que 2 mais o custo do n 2 ao n 3 que 1. Total 3, que menor que 4. Assim a nova etiqueta do n 3 [3,2].

    O arco (2,4) tem custo 5. custo at o n 2 mais o custo do arco (2,4) resulta em 7, que maior que o valor atual do n 4, que 4. Assim o n 4 no muda a etiqueta.

    O n 2 passa a permanente. A lista atual de permanentes e temporrios e:

    P= {1,2} T={3,4,5,6}

    O novo n temporrio de menor custo 3 com etiqueta [3,2]. o novo n k a partir do qual se faz a varredura aos ns temporrios adjacentes.

    No final do algoritmo as etiquetas dos ns sero as seguintes (figura 4.4):

    1

    2

    3

    4 5

    62 2

    4

    4

    5

    5 5

    6 6

    7

    8

    [0, -1]

    [10, 3]

    [8, 4]

    [3, 2]

    [4, 1][2, 1]

    Figura 4.4: Valor final das etiquetas de rota mnima de 1 at todos os ns.

    A partir das etiquetas pode-se construir o vetor de precedentes:

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    31

    Vetor de Precedentes j

    j 1 -1 2 1 3 2 4 1 5 4 6 3

    Este vetor de precedentes corresponde a uma rvore de rota mnima com raiz em 1, como mostrado na figura 4.5.

    1

    2

    3

    4 5

    6

    [0, -1]

    [10, 3]

    [8, 4]

    [3, 2]

    [4, 1][2, 1]

    Figura 4.5: rvore de rota mnima enraizada em 1.

    Com o vetor de precedentes pode-se encontrar o caminho retrocedendo desde cada destino origem, no caso o n 1 do exemplo.

    Formalmente um algoritmo para encontrar rotas apresentado a seguir:

    Rota Retrocedendo de J a 1:

    R: conj. de ns na rota

    R = j

    Repita

    j = [j]

    R RU j

    At j = -1

    Ex.: Rota de 6 a 1:

    R = 6

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    32

    _______________________

    j = [6] =3

    R= {6,3}

    [3] -1 _______________________

    j = [3] = 2

    R = {6, 3, 2}

    [2] -1

    _______________________

    j = [2] =1

    R = {6, 3, 2, 1}

    [1] = -1 : PARE

    De fato olhando-se na figura 4.5 observa-se que o caminho de 1 at 6 passa pelos ns: 1,2,3,6.

    A Complexidade do algoritmo de Djkstra para um grafo completo de ordem 0 (n2), fazendo o clculo de uma origem para todos os destinos

    O algoritmo de Djkstra de um tipo Label setting algorithm, o que poderia ser traduzido com um algoritmo de colocao de etiquetas.

    4. CLCULO DA ROTA MNIMA ENTRE TODOS OS PARES DE NS

    4.1. ALGORITMO DE FLOYD-WARSCHALL

    At agora foram mostrados algoritmos que calculam a rota mnima entre um n e todos os outros ns. Para resolver o problema ara toda a rede necessrio aplicar o algoritmo n vezes, sendo n=|N|. Existe um procedimento para calcular a RM entre todos os pares de ns, proposto por Floyd eWarschall (62)

    Seja i jk( )

    pi = comprimento da RM de i para j sujeito a condio de que o caminho no passe pelos ns intermedirios k, k+1, k+2, ....., n

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    33

    i jn + 1

    pi ser o verdadeiro comprimento de RM

    i jK +1

    pi = min { }i jk i kk k jkpi pi pi, ,( ) ( ) k = 1, 2, ...., n j k i j k

    Seja o caminho que no passa pelos ns k +1, k+2, ...... , n. S h duas alternativas:

    a) Se o caminho no passa n k o comprimento ser: i j

    k( )pi

    b) Passa pelo n k com comprimento i k

    kk jk

    pi pi+( )

    O algoritmo trabalha da seguinte forma:

    Dado um grafo: G (N, A), com NS: 1, ..., n

    Define-se:

    Uma MATRIZ D(k) (n x n) , onde:

    d(i,j): Extenso do caminho entre n i e j, na iterao k do algoritmo

    e uma outra matriz :

    MATRIZ P(k) (n x n), aonde :

    p(i,j) : Predecessor direto do n j no caminho de i a j, na iterao k.

    O algoritmo de Floyd descrito a seguir.

    FLOYD:

    1. Inicializao

    l (i, j) se arco (i,j) existe, d0 (i, j) = 0 se i=j, se arco i, j no existe.

    i se i j se arco i,j existe p0 (i, j) =

    0 se i = j ou se arco i,j no existe.

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    34

    2. Variando k de 1 a n, faa:

    { Atualizar elementos da matriz Dk :} Variando i de 1 a n faa Variando j de 1 a n faa

    dk (i, j) = Min {dk-1 (i, j); dk-1 (i, k) + dk-1 (k, j)

    { Atualizar predecessor}

    pk-1 (k, j) se dk (i, j) dk-1 (i, j) pk (i, j) =

    pk-1 (i, j) caso contrrio

    fim variando j fim variando i fim variando k

    No final do algoritmo tem-se:

    dn (i, j) : Valor da extenso do caminho + curto entre i e j (Quadro 10.8,NOVAES)

    pn (i, j) : Primeiro n precedente de j no caminho entre i e j

    Figura 4.6: Exemplo para o clculo da rota mnima.

    4 8 3 5 2 2 9 4 5 3 4 1 3 6 6 10 1 6 3

    8 3 4 7

    4 3 7

  • MODELOS E MTODOS DE OTIMIZAO EM REDES DE TRANSPORTES JOS EUGENIO LEAL

    35

    Exemplo de MATRIZ p{n}:

    1 2 3 4 5 6 7 8 9 10 1 0 1 1 1 2 3 3 5 6 6 2 3 0 4 7 2 5 10 5 6 6 3 3 1 0 7 6 3 3 9 6 6 4 3 1 4 0 6 3 4 9 6 7 5 3 6 4 7 0 5 10 5 6 6 6 3 6 4 7 6 0 10 9 6 6 7 3 1 4 7 6 3 0 9 10 7 8 0 9 3 6 4 7 6 9 10 9 0 9 10 3 6 4 7 6 9 10 9 10 0

    dn (i, j) = Se no houver caminho entre i e j

    Nesta matriz cada linha corresponde a um vetor de precedentes visto no algoritmo de Djkstra. Ou seja, para encontrar o caminho entre 1 e 9 , trabalha-se somente com a linha 1 da matriz e faz-se: P(1,9)=6 P(1,6)=3 P(1,3)=1.

    Logo o caminho {1,3,6,9} ( linhas mais fortes na figura 5)

    Para o caminho entre 4 e 5 toma-se: P(4,5)=6 P(4,6)=3 P(4,3)=4. O caminho (4,3,6,5), que pode ser visto na figura 5, embora no marcado.

    A Complexidade do algoritmo de Floyd-Warschal n (n-1) (n-2) soma + comparaes, o que d O(n3). Por outro lado ele exige o uso da matriz de distancia pi = (di j) de tamanho nXn. Para n grande, uma rede de certo porte este tamanho da matriz pi proibitivo. Neste caso melhor usar n vezes o algoritmo de Djkstra.

    Para redes com arcos de comprimentos no negativos, di j 0, usar o Djkstra para toda a rede tem complexidade 0 (n3) por repetir n vezes. A vantagem ocupar muito menor espao de memria.

    Para redes com arcos com comprimentos negativos e positivos, di j 0 e di j < 0, pode-se usar um algoritmo de correo de etiquetas com uma modificao, que tambm pode ser de complexidade O (n3).