Pular para o conteúdo principal

Algoritmo de Dijkstra

O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959,[1][2] soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional  onde V é o número de vértices e E é o número de arestas. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford, que possui maior tempo de execução que o Dijkstra.

O algoritmo considera um conjunto S de menores caminhos, iniciado com um vértice inicial I. A cada passo do algoritmo busca-se nas adjacências dos vértices pertencentes a S aquele vértice com menor distância relativa a I e adiciona-o a S e, então, repetindo os passos até que todos os vértices alcançáveis por I estejam em S. Arestas que ligam vértices já pertencentes a S são desconsideradas.

Um exemplo prático de problema que pode ser resolvido pelo algoritmo de Dijkstra é: alguém precisa se deslocar de uma cidade para outra. Para isso, ela dispõe de várias estradas, que passam por diversas cidades. Qual delas oferece uma trajetória de menor caminho?



 https://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra

Postagens mais visitadas deste blog

Recursividade Minha Linda! Estrutura Produtos Protheus SG1

Fato! Depois que você conhece recursividade em sua vida tudo fica mais leve (rss... ) a recursividade pode ser infinita (pode não ta!) se for infinita vai dar problema, não pode. Mas a recursividade nos ajuda a deixar nosso sistema mais flexível e dinâmico para montar uma série de regras de negócio. Hoje vou falar exatamente da SG1, tabela TOTVS Microsiga Protheus que é utilizada para montar a estrutura de um produto dentro PCP (Planejamento e Controle de Produção). Isso séria algo que a recursividade iria ajudar. Na SG1 temos o campos G1_COD (Pai) e G1_COMP (Filho). G1_COD->G1_COMP->G1_COD->G1_COMP->G1_COD->G1_COMP Seria assim o fluxo da informação. Sem mais delongas, abaixo vou deixar o script para MSSQL para apresentar esses dados. Inté! WITH ESTRUT( CODIGO, COD_PAI, COD_COMP, QTD, PERDA, DT_INI, DT_FIM ,TRT ,RECNO, NIVEL ) AS ( SELECT G1_COD PAI, G1_COD, G1_COMP, G1_QUANT, G1_PERDA, G1_INI, G1_FIM,G1_TRT,SG1.R_E_C_N_O_, 1 AS NIVEL FR...
Leia mais

REST Protheus Converter charset CP1252 para UTF8 com Header Accept UTF-8

O Protheus possui um tag que pode ser utilizada para conversão para UTF8 de forma transparente, basta enviar no header da requisição a TAG ACCEPT com charset=UTF-8, também pode-se adicionar o appllication/json. Accept : application/json; charset=UTF-8 ou Accept : charset=UTF-8 Isso ajuda pois não precisa mais utilizar as funções DecodeUTF8 e EncodeUT8 pois o próprio rest já vai fazer isso.
Leia mais

Cadastro de funções ADVPL

FWDirRemove( cDir, nType, lComplete, lKillFiles ) Função para remover diretórios, com a vantagem de remover somente o ultimo nível ou todo o caminho. cDir                   Diretório a ser removido lComplete          Remove todo o caminho (.T.) ou apenas o ultimo nível (.F.) lKillFiles             Remove os arquivos antes de tentar remover o diretório FWMakeDir( cDir, lShowMsg ) Função para criar diretório com seus subdiretórios, com a vantagem de criar todo o caminho. cDir                    Diretório a ser criado lShowMsg          Exibe ou não mensagem caso não consiga criar o diretório FwNoAccent( cString ) Retira acentos de uma string cString ...
Leia mais