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

SB9 Protheus x Fechamentos incorretos (Sem endereço ou lote)

Uebá!!! Montei essa query um tempo atrás para localizar fechamento incorreto no protheus, o fechamento acontece na SB9, que é feito todo mês. Let's Share! https://centraldeatendimento.totvs.com/hc/pt-br/articles/360006558492-MP-SIGAEST-Roteiro-para-a-realiza%C3%A7%C3%A3o-da-virada-de-saldos-no-estoque-MATA280 SELECT * FROM ( SELECT B9_FILIAL,B9_COD,B9_LOCAL,B9_DATA,B9_QINI, --ULTIMO FECHAMENTO ANTES DO MES ATUAL ( SELECT ISNULL(B9_QINI,0) FROM SB9050 SB9X WHERE SB9X.B9_COD =SB9.B9_COD AND SB9X.B9_LOCAL = SB9.B9_LOCAL AND SB9X.D_E_L_E_T_ = ' ' AND MONTH(SB9X.B9_DATA) = MONTH(DATEADD(month,-1,convert(datetime,SB9.B9_DATA,103))) AND YEAR(SB9X.B9_DATA) = YEAR(DATEADD(month,-1,convert(datetime,SB9.B9_DATA,103))) --SELECT * FROM SF4050 WHERE F4_CODIGO = '618' )-( --MOVIMENTACAO DO ESTOQUE SELECT ISNULL(SUM(CASE WHEN LEFT(SD3.D3_CF,1)='R' THEN SD3.D3_QUANT ELSE SD3.D3_QUANT * -1 END),0) FROM S...
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