• A menor distância entre dois pontos. Você sabe por que está mais longe em linha reta do que em arco? Determinando a distância entre duas linhas de interseção

    01.02.2022

    Tendo traçado dois pontos no quadro-negro com giz, o professor oferece ao jovem aluno uma tarefa: traçar o caminho mais curto entre os dois pontos.

    O aluno, depois de pensar, desenha diligentemente uma linha sinuosa entre eles.

    - Esse é o caminho mais curto! a professora fica surpresa. - Quem te ensinou isso?

    - Meu pai. Ele é um taxista.

    O desenho de um estudante ingênuo é, claro, anedótico, mas você não sorriria se lhe dissessem que o arco pontilhado na fig. 1 é o caminho mais curto do Cabo da Boa Esperança até o extremo sul da Austrália!

    Ainda mais impressionante é a seguinte afirmação: representada na Fig. 2 ida e volta do Japão ao Canal do Panamá é mais curta que a linha reta traçada entre eles no mesmo mapa!

    Arroz. 1. Em uma carta náutica, a rota mais curta do Cabo da Boa Esperança até o extremo sul da Austrália não é indicada por uma linha reta (“loxodrome”), mas por uma curva (“ortodromia”)


    Tudo isso parece uma piada, mas enquanto isso diante de vocês estão verdades indiscutíveis, bem conhecidas dos cartógrafos.




    Arroz. 2. Parece incrível que o caminho curvo que liga Yokohama na carta marítima com o Canal do Panamá seja mais curto do que uma linha reta traçada entre os mesmos pontos


    Para esclarecer a questão, algumas palavras terão que ser ditas sobre as cartas em geral e sobre as cartas náuticas em particular. Descrever partes da superfície da Terra no papel não é tarefa fácil, mesmo em princípio, porque a Terra é uma esfera, e sabe-se que nenhuma parte da superfície esférica pode ser desdobrada em um plano sem dobras e quebras. Involuntariamente, é preciso tolerar as inevitáveis ​​distorções nos mapas. Muitas maneiras de desenhar mapas foram inventadas, mas nem todos os mapas estão livres de falhas: alguns têm distorções de um tipo, outros de um tipo diferente, mas não há mapas sem distorções.

    Os marinheiros usam mapas desenhados de acordo com o método de um antigo cartógrafo e matemático holandês do século XVI. Mercator. Este método é chamado de projeção de Mercator. É fácil reconhecer uma carta marítima por sua grade retangular: os meridianos são mostrados nela como uma série de linhas retas paralelas; círculos de latitude - também em linhas retas perpendiculares ao primeiro (ver Fig. 5).

    Imagine agora que você deseja encontrar o caminho mais curto de um porto oceânico para outro no mesmo paralelo. No oceano, todos os caminhos estão disponíveis, e sempre é possível viajar pelo caminho mais curto, se você souber como ele fica. No nosso caso, é natural pensar que o caminho mais curto percorre o paralelo em que se encontram os dois portos: afinal, no mapa é uma linha reta, e o que pode ser mais curto que um caminho reto! Mas estamos enganados: o caminho ao longo do paralelo não é nada dos mais curtos.

    De fato: na superfície de uma esfera, a distância mais curta entre dois pontos é o arco do grande círculo que os conecta. Mas o círculo de paralelo pequena um círculo. O arco de um círculo grande é menos curvo que o arco de qualquer círculo pequeno desenhado pelos mesmos dois pontos: um raio maior corresponde a uma curvatura menor. Puxe o fio do globo entre os nossos dois pontos (cf. Fig. 3); você se certificará de que ele não fique ao longo do paralelo. Um fio esticado é um indicador indiscutível do caminho mais curto e, se não coincidir com um paralelo em um globo, em um mapa marítimo o caminho mais curto não é indicado por uma linha reta: lembre-se de que os círculos de paralelos são representados em tal um mapa por linhas retas, qualquer linha que não coincida com uma linha reta, existe curva .



    Arroz. 3. Uma maneira simples de encontrar o caminho realmente mais curto entre dois pontos: você precisa puxar um fio no globo entre esses pontos


    Depois do que foi dito, fica claro por que o caminho mais curto na carta marítima é representado não como uma linha reta, mas como uma linha curva.

    Eles dizem que, ao escolher a direção da ferrovia Nikolaev (agora Oktyabrskaya), houve intermináveis ​​disputas sobre qual caminho colocá-la. As disputas foram encerradas pela intervenção do czar Nicolau I, que resolveu o problema literalmente “simplesmente”: ele conectou São Petersburgo a Moscou ao longo da linha. Se isso tivesse sido feito em um mapa de Mercator, teria sido uma surpresa embaraçosa: em vez de uma linha reta, a estrada seria uma curva.

    Quem não evita os cálculos pode convencer-se por um simples cálculo de que o caminho que nos parece curvo no mapa é na verdade mais curto do que aquele que estamos prontos para considerar reto. Deixe nossos dois portos ficarem no paralelo 60º e separados por uma distância de 60º. (Se esses dois portos realmente existem é, obviamente, irrelevante para o cálculo.)



    Arroz. 4. Para o cálculo das distâncias entre os pontos A e B na bola ao longo do arco do paralelo e ao longo do arco do grande círculo


    Na fig. 4 pontos O- centro do globo, AB- o arco do círculo de latitude em que se encontram os portos A e B; dentro ela 60°. O centro do círculo de latitude está em um ponto A PARTIR DE Imagine que do centro O do globo é traçado pelos mesmos portos um grande arco de círculo: seu raio OB = OA = R; ele passará próximo ao arco desenhado AB, mas não combina.

    Vamos calcular o comprimento de cada arco. Já que os pontos MAS e NO situar-se a uma latitude de 60°, então os raios OA e OV fazer as pazes com SO(o eixo do globo) um ângulo de 30°. Em um triângulo retângulo ASO perna CA (=r), oposto a um ângulo de 30° é igual a metade da hipotenusa JSC;

    significa, r=R/2 Comprimento do arco ABé um sexto do comprimento do círculo de latitude, e como este círculo tem metade do comprimento do círculo grande (correspondendo à metade do raio), então o comprimento do arco do círculo pequeno



    Para determinar agora o comprimento do arco de um grande círculo desenhado entre os mesmos pontos (ou seja, o caminho mais curto entre eles), precisamos saber a magnitude do ângulo AOW. Acorde COMO, subtraindo o arco a 60° (círculo pequeno), é o lado de um hexágono regular inscrito no mesmo pequeno círculo; é por isso AB \u003d r \u003d R/2

    Desenhando uma linha reta ah, centro de conexão O o globo com o meio D acordes AB, obter um triângulo retângulo ODA, onde está o ângulo D- direto:

    DA= 1/2 AB e OA=R.

    sinAOD=AD: AO=R/4:R=0,25

    A partir daqui encontramos (de acordo com as tabelas):

    =14°28",5

    e, portanto

    = 28°57".

    Agora não é difícil encontrar o comprimento desejado do caminho mais curto em quilômetros. O cálculo pode ser simplificado se lembrarmos que a duração de um minuto de um grande círculo do globo é

    Aprendemos que o caminho ao longo do círculo de latitude, mostrado na carta marítima por uma linha reta, é de 3333 km, e o caminho ao longo do círculo grande - ao longo da curva no mapa - 3213 km, ou seja, 120 km mais curto.

    Armado com um fio e um globo à mão, você pode facilmente verificar a exatidão de nossos desenhos e certificar-se de que os arcos dos grandes círculos realmente estão conforme mostrado nos desenhos. Mostrado na fig. 1 como se a rota marítima "reta" da África para a Austrália fosse 6020 milhas, e a "curva" - 5450 milhas, ou seja, mais curta em 570 milhas ou 1050 km. A rota aérea "direta" na carta marítima de Londres a Xangai corta o Mar Cáspio, enquanto a rota realmente mais curta fica ao norte de São Petersburgo. Está claro o papel que essas questões desempenham na economia de tempo e combustível.

    Se na era da navegação à vela o tempo nem sempre era valorizado - então o "tempo" ainda não era considerado "dinheiro", então, com o advento dos navios a vapor, é preciso pagar por cada tonelada extra de carvão consumida. É por isso que em nossos dias os navios estão navegando pelo caminho realmente mais curto, muitas vezes usando mapas feitos não no Mercator, mas na chamada projeção "central": nesses mapas, os arcos de grandes círculos são representados como linhas retas.

    Por que, então, antigos navegadores usaram mapas tão enganosos e escolheram caminhos desfavoráveis? É um erro pensar que antigamente eles não sabiam da característica agora indicada das cartas marítimas. A questão é explicada, é claro, não por isso, mas pelo fato de que as cartas desenhadas de acordo com o método de Mercator, juntamente com os inconvenientes, trazem benefícios muito valiosos para os marinheiros. Tal mapa, em primeiro lugar, retrata pequenas partes separadas da superfície terrestre sem distorção, preservando os cantos do contorno. Isso não é contrariado pelo fato de que, com a distância do equador, todos os contornos são visivelmente esticados. Em altas latitudes, o trecho é tão significativo que uma carta marítima inspira uma pessoa que não conhece suas características com uma ideia completamente falsa do verdadeiro tamanho dos continentes: a Groenlândia parece ter o mesmo tamanho da África, do Alasca é maior que a Austrália, embora a Groenlândia seja 15 vezes menor que a África, e o Alasca, juntamente com a Groenlândia, tenha metade do tamanho da Austrália. Mas um marinheiro que está bem familiarizado com essas características da carta não pode ser enganado por elas. Ele os tolera, especialmente porque, dentro de pequenas áreas, uma carta marítima dá uma exata semelhança com a natureza (Fig. 5).

    Por outro lado, a carta marítima facilita muito a solução das tarefas da prática navegacional. Este é o único tipo de carta em que o caminho de um navio em um curso constante é representado como uma linha reta. Seguir um "curso constante" significa manter invariavelmente uma direção, uma "romba" definida, em outras palavras, ir de modo a cruzar todos os meridianos em um ângulo igual. Mas este caminho ("loxodrome") pode ser descrito como uma linha reta apenas em um mapa no qual todos os meridianos são linhas retas paralelas entre si. E como no globo os círculos de latitude se cruzam com os meridianos em ângulos retos, em tal mapa os círculos de latitude devem ser linhas retas perpendiculares às linhas dos meridianos. Em suma, chegamos precisamente à grelha de coordenadas que constitui um traço característico da carta marítima.




    Arroz. 5. Mapa náutico ou Mercator do globo. Nesses mapas, as dimensões dos contornos distantes do equador são muito exageradas. Qual, por exemplo, é maior: Groenlândia ou Austrália? (resposta no texto)


    A predileção dos marinheiros pelos mapas de Mercator agora é compreensível. Querendo determinar o rumo a ser seguido ao chegar ao porto designado, o navegador aplica uma régua nos pontos finais do caminho e mede o ângulo que ele faz com os meridianos. Mantendo-se em mar aberto o tempo todo nessa direção, o navegador levará com precisão o navio ao alvo. Você vê que o “loxodrome” é, embora não seja o mais curto e nem o mais econômico, mas de certa forma uma maneira muito conveniente para um marinheiro. Para chegar, por exemplo, do Cabo da Boa Esperança ao extremo sul da Austrália (ver Fig. 1), deve-se sempre manter o mesmo rumo S 87°, 50". ponto final no caminho mais curto (ao longo do" ”), é necessário, como pode ser visto na figura, mudar continuamente o curso da embarcação: comece no curso S 42 °, 50 "e termine com o curso N 53 °. 50" (neste caso, o caminho mais curto nem é viável - repousa sobre a parede de gelo da Antártida).

    Ambos os caminhos - ao longo do "loxodrome" e ao longo da "ortodromia" - coincidem apenas quando o caminho ao longo do grande círculo é representado na carta marítima como uma linha reta: ao se mover ao longo do equador ou ao longo do meridiano. Em todos os outros casos, esses caminhos são diferentes.

    (Geometria Descritiva)
  • CD (CXDX, C2D2) exibido como um ponto C5 = D5 A5B5é igual a...
    (Geometria Descritiva)
  • Determinando a distância entre dois planos paralelos
    Determinação da distância entre dois planos paralelos na posição geral 01| X convém reduzi-lo ao problema de determinar a distância entre os mesmos dois planos, transformados na posição dos que se projetam. Neste caso, a distância entre os planos é definida como a perpendicular entre as linhas, ...
    (Geometria Descritiva)
  • Determinando a distância entre duas linhas de interseção
    Se você deseja determinar a distância mais curta entre duas linhas de interseção, você deve alterar os sistemas de planos de projeção duas vezes. Ao resolver este problema, o CD (CXDX, C2D2) exibido como um ponto C5 = D5(Fig. 198). Distância deste ponto até a projeção A5B5é igual a...
    (Geometria Descritiva)
  • Ângulo entre duas retas que se cruzam
    Este é o ângulo entre duas linhas de interseção que são paralelas aos dados. Assim, esta tarefa é semelhante à anterior. Para resolvê-lo, você precisa pegar um ponto arbitrário e desenhar duas linhas retas através dele, paralelas às linhas retas inclinadas dadas, e usando transformações de projeção, determinar o ângulo desejado....
    (Fundamentos de geometria descritiva. Um curso curto e uma coleção de problemas.)
  • Determinando a distância entre duas linhas paralelas
    O problema é resolvido pelo método de dupla substituição dos planos de projeção. Na etapa final, um dos planos de projeção deve ser perpendicular a uma das linhas de interseção. Então a distância mais curta entre eles é determinada pelo valor do segmento da perpendicular à outra linha de inclinação (Fig. 199)....
    (Geometria Descritiva)
  • O caminho ao longo da linha pontilhada na imagem é mais curto do que o caminho ao longo da linha sólida. E agora um pouco mais detalhadamente sobre o exemplo das rotas marítimas:

    Se você navegar em um curso constante, a trajetória do navio na superfície da Terra será uma curva, chamada em matemática logarítmicoespiral.

    Na navegação, essa complexa linha de dupla curvatura é chamada loxodromia, que em grego significa "corrida oblíqua".

    No entanto, a distância mais curta entre dois pontos no globo é medida ao longo do arco de um grande círculo.

    O arco de um grande círculo é obtido como um traço da intersecção da superfície da Terra com um plano que passa pelo centro da Terra, tomado como uma bola.

    Na navegação, o grande arco de círculo é chamado grande círculo, que significa "correr em linha reta". A segunda característica do grande círculo é que ele cruza os meridianos em diferentes ângulos (Fig. 29).

    A diferença nas distâncias entre dois pontos na superfície da Terra ao longo do loxodromo e ortódromo é de importância prática apenas para grandes travessias oceânicas.

    Em condições normais, essa diferença é desprezada e a navegação é realizada em um curso constante, ou seja, por loxodromo.

    Para derivar a equação, tomamos loxodromias (Fig. 30, uma) dois pontos MAS e NO, a distância entre eles é simplesmente pequena. Desenhando meridianos e um paralelo através deles, obtemos um triângulo esférico de ângulo reto elementar ABC. Neste triângulo, o ângulo formado pela interseção do meridiano e do paralelo é reto, e o ângulo PnAB igual ao curso do navio K. Katet CA representa um segmento de arco meridiano e pode ser expresso

    Onde R - raio da Terra tomado como uma esfera;

    Δφ - incremento elementar de latitude (diferença de latitudes).

    perna SO representa um segmento de arco paralelo

    onde r - raio do paralelo;

    Δλ - diferença elementar de longitudes.

    Do triângulo OO 1 C pode ser encontrado que

    Então na forma final a perna SO pode ser expresso assim:

    Supondo um triângulo esférico elementar abc para apartamento, escreva

    Após redução R e substituindo pequenos incrementos elementares de coordenadas por infinitesimais, temos

    Integramos a expressão resultante no intervalo de φ 1, λ 1 a φ 2, λ 2 considerando o valor de tgK como um valor constante:

    No lado direito temos uma integral tabular. Depois de substituir seu valor, obtemos a equação loxodrome na bola

    A análise desta equação permite-nos tirar as seguintes conclusões:

    Nos cursos de 0 e 180 °, o loxodrome se transforma em um arco de grande círculo - um meridiano;

    Nos cursos de 90 e 270 °, o loxodrome coincide com o paralelo;

    O loxodromo cruza cada paralelo apenas uma vez, e cada meridiano um número incontável de vezes. Essa. aproximando-se em espiral do pólo, não o alcança.

    A navegação em curso constante, ou seja, ao longo do loxodromo, embora não seja a distância mais curta entre dois pontos da Terra, representa uma conveniência considerável para o navegador.

    Os requisitos para uma carta de navegação marítima podem ser formulados com base na vantagem da navegação ao longo do loxodromo e nos resultados da análise de sua equação como segue.

    1. Loxodrome, cruzando os meridianos em um ângulo constante, deve ser representado como uma linha reta.

    2. A projecção cartográfica utilizada para a construção das cartas deve ser conforme de modo a que os rumos, azimutes e ângulos que nela se encontrem correspondam ao seu valor no terreno.

    3. Meridianos e paralelos, como as linhas de curso 0, 90, 180° e 270°, devem ser retas perpendiculares entre si.

    A menor distância entre dois pontos dados na superfície da Terra, tomada como uma esfera, é o menor dos arcos de um grande círculo que passa por esses pontos. Exceto no caso de um navio seguindo um meridiano ou o equador, o grande círculo cruza os meridianos em diferentes ângulos. Portanto, um navio seguindo tal curva deve mudar seu curso o tempo todo. É praticamente mais conveniente seguir um curso que faz um ângulo constante com os meridianos e é representado no mapa na projeção de Mercator por uma linha reta - loxodrome. No entanto, a grandes distâncias, a diferença no comprimento da ortódromo e loxodromo atinge um valor significativo. Portanto, nesses casos, o ortódromo é calculado e pontos intermediários são marcados nele, entre os quais nadam ao longo da loxódromo.

    Uma projeção cartográfica que atende aos requisitos acima foi proposta pelo cartógrafo holandês Gerard Cramer (Mercator) em 1569. Em homenagem ao seu criador, a projeção recebeu o nome de Mercator.

    E quem quiser aprender informações ainda mais interessantes saiba mais O artigo original está no site InfoGlaz.rf Link para o artigo do qual esta cópia é feita -

    DISTÂNCIA, distâncias, cf. 1. Um espaço separando dois pontos, uma lacuna entre algo. A menor distância entre dois pontos em uma linha reta. Vive de nós a uma distância de dois quilômetros. “O comandante os deixou entrar na distância mais próxima ... Dicionário explicativo de Ushakov

    distância- substantivo, s., uso. frequentemente Morfologia: (não) o quê? distância para quê? distância, (ver) o quê? distância do que? distância, o quê? sobre distância; pl. que? distância, (não) o quê? distâncias, por quê? distâncias, (ver) o quê? distância do que? distâncias... Dicionário de Dmitriev

    distância- EU; cf. O espaço que separa dois pontos, dois objetos, etc., o espaço entre alguém, que l. O rio mais curto entre dois pontos. R. de casa para a escola. Retire-se para um rio próximo. A uma distância de um metro, braços estendidos. Saiba algo, sinta algo. no… … dicionário enciclopédico

    distância- EU; cf. Veja também distância a) O espaço que separa dois pontos, dois objetos, etc., a distância entre alguém, do que l. A menor distância entre dois pontos. Distância de casa à escola. Retire-se para uma distância próxima / nie ... Dicionário de muitas expressões

    GEOMETRIA- um ramo da matemática que estuda as propriedades de várias formas (pontos, linhas, ângulos, objetos bidimensionais e tridimensionais), seu tamanho e posição relativa. Para facilitar o ensino, a geometria é dividida em planimetria e geometria sólida. NO… … Enciclopédia Collier

    Navegação*

    Navegação- departamento de navegação (ver), concluindo uma apresentação das formas de determinar a localização de um navio no mar, utilizando uma bússola e um log (ver). Determinar a localização do navio no mar significa colocar no mapa o ponto em que o navio se encontra atualmente. ... ... Dicionário Enciclopédico F.A. Brockhaus e I.A. Efron

    COGEN- (Cohen) Hermann (1842 1918) Filósofo alemão, fundador e proeminente representante da escola de neokantismo de Marburg. Principais obras: 'Teoria da Experiência de Kant' (1885), 'Justificação da Ética de Kant' (1877), 'Justificação da Estética de Kant' (1889), 'Lógica... ...

    Kant Emanuel- Caminho de vida e escritos de Kant Immanuel Kant nasceu em Königsberg (agora Kaliningrado) na Prússia Oriental em 1724. Seu pai era um seleiro e sua mãe era dona de casa, seis de seus filhos não chegaram à idade adulta. Kant sempre se lembrava de seus pais com ... ... A filosofia ocidental desde suas origens até os dias atuais

    A FILOSOFIA CRÍTICA DE KANT: A DOUTRINA DAS HABILIDADES- (La philosophie critique de Kant: Doctrines des facultes, 1963) por Deleuze. Descrevendo o método transcendental na introdução, Deleuze observa que Kant entende a filosofia como a ciência da relação de todo conhecimento com objetivos essenciais... ... História da Filosofia: Enciclopédia

    princípio da fazenda- o princípio básico da óptica geométrica (ver óptica geométrica). A forma mais simples de F. p. é a afirmação de que um raio de luz sempre se propaga no espaço entre dois pontos ao longo do caminho ao longo do qual o tempo de sua passagem é menor que ... Grande Enciclopédia Soviética

    O algoritmo de Dijkstra é um algoritmo gráfico inventado pelo cientista holandês Edsger Dijkstra em 1959. Encontra os caminhos mais curtos de um dos vértices do grafo para todos os outros. O algoritmo funciona apenas para grafos sem arestas de peso negativo.

    Considere a execução do algoritmo no exemplo do gráfico mostrado na figura.

    Seja necessário encontrar as distâncias mais curtas do 1º vértice a todos os outros.

    Os círculos indicam os vértices, as linhas indicam os caminhos entre eles (as arestas do gráfico). Os números dos vértices são indicados nos círculos, seu "preço" - o comprimento do caminho - é indicado acima das bordas. Ao lado de cada vértice, um rótulo vermelho é marcado - o comprimento do caminho mais curto para esse vértice a partir do vértice 1.

    Primeiro passo. Considere um passo no algoritmo de Dijkstra para o nosso exemplo. O vértice 1 tem o rótulo mínimo e os vértices 2, 3 e 6 são seus vizinhos.

    O primeiro vizinho do vértice 1, por sua vez, é o vértice 2, porque o comprimento do caminho para ele é mínimo. O comprimento do caminho para ele através do vértice 1 é igual à soma do valor do rótulo do vértice 1 e o comprimento da aresta que vai do 1º ao 2º, ou seja, 0 + 7 = 7. Isso é menor que o rótulo atual do vértice 2, infinito, então o novo rótulo do 2º vértice é 7.

    Realizamos uma operação semelhante com outros dois vizinhos do 1º vértice - o 3º e o 6º.

    Todos os vizinhos do nó 1 são verificados. A distância mínima atual para o pico 1 é considerada final e não está sujeita a revisão (o fato de que este é realmente o caso foi provado pela primeira vez por E. Dijkstra). Cruze-o fora do gráfico para marcar que este vértice foi visitado.

    Segundo passo. A etapa do algoritmo é repetida. Novamente encontramos o “mais próximo” dos vértices não visitados. Este é o vértice 2 rotulado como 7.

    Novamente tentamos reduzir os rótulos dos vizinhos do vértice selecionado, tentando passar por eles pelo 2º vértice. Os vizinhos do vértice 2 são os vértices 1, 3 e 4.

    O primeiro vizinho (em ordem) do vértice 2 é o vértice 1. Mas já foi visitado, então não fazemos nada com o 1º vértice.

    O próximo vizinho do vértice 2 é o vértice 3, pois possui o rótulo mínimo dos vértices marcados como não visitados. Se você passar por 2, o comprimento desse caminho será igual a 17 (7 + 10 = 17). Mas o rótulo atual do terceiro vértice é 9, que é menor que 17, então o rótulo não muda.

    Outro vizinho do vértice 2 é o vértice 4. Se você passar pelo 2º, o comprimento desse caminho será igual à soma da distância mais curta até o 2º vértice e a distância entre os vértices 2 e 4, ou seja , 22 (7 + 15 = 22) . Desde 22<, устанавливаем метку вершины 4 равной 22.

    Todos os vizinhos do vértice 2 foram visualizados, congelamos a distância até ele e marcamos como visitado.

    Terceiro passo. Repetimos o passo do algoritmo selecionando o vértice 3. Após seu “processamento”, obtemos os seguintes resultados:

    Próximos passos. Repetimos o passo do algoritmo para os vértices restantes. Estes serão os vértices 6, 4 e 5, respectivamente.

    Conclusão da execução do algoritmo. O algoritmo termina quando não é possível processar mais vértices. Neste exemplo, todos os vértices estão riscados, mas é um erro supor que esse será o caso em qualquer exemplo - alguns vértices podem permanecer não riscados se não puderem ser alcançados, ou seja, se o grafo estiver desconectado. O resultado do algoritmo é visível na última figura: o caminho mais curto do vértice 1 a 2 é 7, a 3 é 9, a 4 é 20, a 5 é 20, a 6 é 11.

    Implementação do algoritmo em várias linguagens de programação:

    C++

    #include "stdafx.h" #include usando o namespace std; const int V=6; // Algoritmo de Dijkstra void Dijkstra(int GR[V][V], int st) ( int distância[V], contagem, índice, i, u, m=st+1; bool visitado[V]; for (i= 0 eu "< "<> "; cin>>start; Dijkstra(GR, start-1); system("pause>>void"); )

    Pascal

    programa DijkstraAlgorithm; usacrt; constV=6; inf=100000; tipo vetor=matriz de inteiro; var início: inteiro; const GR: matriz de inteiro=((0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0, 0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); (algoritmo de Dijkstra) procedure Dijkstra(GR: array de inteiro; st: inteiro); var contagem, índice, i, u, m, min: inteiro; vetor de distância; visitou: array de boolean; inicio:=st; para i:=1 até V comece a distância[i]:=inf; visitado[i]:=false; fim; distância:=0; para contagem:=1 a V-1 comece min:=inf; para i:=1 a V faça se (não visitado[i]) e (distância[i]<=min) then begin min:=distance[i]; index:=i; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[i]) and (GR<>0) e (distância[u]<>inf) e (distância[u]+GR inf then writeln(m," > ", i," = ", distance[i]) else writeln(m," > ", i," = ", "rota indisponível"); fim; (bloco de programa principal) begin clrscr; write("Iniciando nó >> "); leia(começar); Dijkstra(GR, iniciar); fim.

    Java

    import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; importar java.util.Arrays; importar java.util.StringTokenizer; public class Solution ( private static int INF = Integer.MAX_VALUE / 2; private int n; //número de vértices no dígrafo private int m; //número de arcos no dígrafo private ArrayList adj; //lista de adjacências private ArrayList peso; //peso da aresta no dígrafo private boolean usado; //array para armazenar informações sobre picos passados ​​e não passados ​​private int dist; //array para armazenar a distância do vértice inicial //um array de ancestrais necessários para restaurar o caminho mais curto do vértice inicial private int pred; int início; //vértice inicial, a partir do qual a distância para todos os outros é pesquisada private BufferedReader cin; cout PrintWriter privado; tokenizer StringTokenizer privado; //procedimento para iniciar o algoritmo de Dijkstra a partir do vértice inicial private void dejkstra(int s) ( dist[s] = 0; //a menor distância até o vértice inicial é 0 for (int iter = 0; iter< n; ++iter) { int v = -1; int distV = INF; //выбираем вершину, кратчайшее расстояние до которого еще не найдено for (int i = 0; i < n; ++i) { if (used[i]) { continue; } if (distV < dist[i]) { continue; } v = i; distV = dist[i]; } //рассматриваем все дуги, исходящие из найденной вершины for (int i = 0; i < adj[v].size(); ++i) { int u = adj[v].get(i); int weightU = weight[v].get(i); //релаксация вершины if (dist[v] + weightU < dist[u]) { dist[u] = dist[v] + weightU; pred[u] = v; } } //помечаем вершину v просмотренной, до нее найдено кратчайшее расстояние used[v] = true; } } //процедура считывания входных данных с консоли private void readData() throws IOException { cin = new BufferedReader(new InputStreamReader(System.in)); cout = new PrintWriter(System.out); tokenizer = new StringTokenizer(cin.readLine()); n = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа m = Integer.parseInt(tokenizer.nextToken()); //считываем количество ребер графа start = Integer.parseInt(tokenizer.nextToken()) - 1; //инициализируем списка смежности графа размерности n adj = new ArrayList[n]; for (int i = 0; i < n; ++i) { adj[i] = new ArrayList(); ) //inicializando a lista que armazena os pesos das arestas weight = new ArrayList[n]; para (int i = 0; i< n; ++i) { weight[i] = new ArrayList(); ) // lê o gráfico dado pela lista de arestas for (int i = 0; i< m; ++i) { tokenizer = new StringTokenizer(cin.readLine()); int u = Integer.parseInt(tokenizer.nextToken()); int v = Integer.parseInt(tokenizer.nextToken()); int w = Integer.parseInt(tokenizer.nextToken()); u--; v--; adj[u].add(v); weight[u].add(w); } used = new boolean[n]; Arrays.fill(used, false); pred = new int[n]; Arrays.fill(pred, -1); dist = new int[n]; Arrays.fill(dist, INF); } //процедура восстановления кратчайшего пути по массиву предком void printWay(int v) { if (v == -1) { return; } printWay(pred[v]); cout.print((v + 1) + " "); } //процедура вывода данных в консоль private void printData() throws IOException { for (int v = 0; v < n; ++v) { if (dist[v] != INF) { cout.print(dist[v] + " "); } else { cout.print("-1 "); } } cout.println(); for (int v = 0; v < n; ++v) { cout.print((v + 1) + ": "); if (dist[v] != INF) { printWay(v); } cout.println(); } cin.close(); cout.close(); } private void run() throws IOException { readData(); dejkstra(start); printData(); cin.close(); cout.close(); } public static void main(String args) throws IOException { Solution solution = new Solution(); solution.run(); } }

    Outra opção:

    Importar java.io.*; import java.util.*; public class Dijkstra ( private static final Graph.Edge GRAPH = ( new Graph.Edge("a", "b", 7), new Graph.Edge("a", "c", 9), new Graph.Edge( "a", "f", 14), new Graph.Edge("b", "c", 10), new Graph.Edge("b", "d", 15), new Graph.Edge("c ", "d", 11), new Graph.Edge("c", "f", 2), new Graph.Edge("d", "e", 6), new Graph.Edge("e", "f", 9), ); private static final String START = "a"; private static final String END = "e"; public static void main(String args) ( Graph g = new Graph(GRAPH); g.dijkstra (START); g.printPath(END); //g.printAllPaths(); ) ) class Graph ( private final Map gráfico; // mapeamento de nomes de vértices para objetos Vertex, construídos a partir de um conjunto de Arestas /** Uma aresta do gráfico (usada apenas pelo construtor Graph) */ public static class Edge ( public final String v1, v2; public final int dist; public Edge(String v1, String v2, int dist) ( this.v1 = v1; this.v2 = v2; this.dist = dist; ) ) /** Um vértice do gráfico, completo com mapeamentos para vértices vizinhos */ classe estática pública Vertex implementa Comparable ( public final String name; public int dist = Integer.MAX_VALUE; // MAX_VALUE assumido como infinito public Vertex anterior = null; public final Map vizinhos = novo HashMap<>(); public Vertex(String name) ( this.name = name; ) private void printPath() ( if (this == this.previous) ( System.out.printf("%s", this.name); ) else if ( this.previous == null) ( System.out.printf("%s(unreached)", this.name); ) else ( this.previous.printPath(); System.out.printf(" -> %s( %d)", this.name, this.dist); ) ) public int compareTo(Vertex other) ( return Integer.compare(dist, other.dist); ) ) ) /** Cria um gráfico a partir de um conjunto de arestas * / public Graph(Edge edge) ( graph = new HashMap<>(arestas.comprimento); //uma passagem para encontrar todos os vértices para (Edge e: edge) ( if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1)); if (!graph. containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2)); ) //outra passagem para definir vértices vizinhos para (Edge e: edge) ( graph.get(e.v1). vizinhos.put(graph.get(e.v2), e.dist); //graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // também faça isso para um gráfico não direcionado ) ) /** Executa o dijkstra usando um vértice de origem especificado */ public void dijkstra(String startName) ( if (!graph.containsKey(startName)) ( System.err.printf("Graph don't contém o vértice inicial \"%s\"\n", startName); return; ) final Vertex source = graph.get(startName); NavigableSet q = novo TreeSet<>(); // configura vértices para (Vertex v: graph.values()) ( v.previous = v == source ? source: null; v.dist = v == source ? 0: Integer.MAX_VALUE; q.add( v); ) dijkstra(q); ) /** Implementação do algoritmo de dijkstra usando um heap binário. */ private void dijkstra(final NavigableSet q) ( Vértice u, v; while (!q.isEmpty()) ( u = q.pollFirst(); // vértice com distância mais curta (a primeira iteração retornará a fonte) if (u.dist == Integer.MAX_VALUE) break; // podemos ignorar u (e quaisquer outros vértices restantes) já que eles são inalcançáveis ​​// olha as distâncias para cada vizinho para (Map.Entry a: u.neighbours.entrySet()) ( v = a.getKey(); //o vizinho nesta iteração final int alternateDist = u.dist + a.getValue(); if (alternateDist< v.dist) { // shorter path to neighbour found q.remove(v); v.dist = alternateDist; v.previous = u; q.add(v); } } } } /** Prints a path from the source to the specified vertex */ public void printPath(String endName) { if (!graph.containsKey(endName)) { System.err.printf("Graph doesn"t contain end vertex \"%s\"\n", endName); return; } graph.get(endName).printPath(); System.out.println(); } /** Prints the path from the source to every vertex (output order is not guaranteed) */ public void printAllPaths() { for (Vertex v: graph.values()) { v.printPath(); System.out.println(); } } }

    C

    #incluir #incluir #incluir //#define BIG_EXAMPLE typedef struct node_t node_t, *heap_t; typedef struct borda_t borda_t; struct edge_t ( node_t *nd; /* destino desta aresta */ edge_t *irmão;/* para lista encadeada simples */ int len; /* custo da aresta */ ); struct node_t ( edge_t *edge; /* lista de arestas encadeadas individualmente */ node_t *via; /* onde o nó anterior está no caminho mais curto */ double dist; /* distância do nó de origem */ char name; /* the, er , name */ int heap_idx; /* link para a posição do heap para atualização da distância */ ); /* --- gerenciamento de borda --- */ #ifdef BIG_EXAMPLE # define BLOCK_SIZE (1024 * 32 - 1) #else # define BLOCK_SIZE 15 #endif edge_t *edge_root = 0, *e_next = 0; /* Não se importe com o gerenciamento de memória, eles estão além do ponto. Finja e_next = malloc(sizeof(edge_t)) */ void add_edge(node_t *a, node_t *b, double d) ( if (e_next == edge_root ) ( edge_root = malloc(sizeof(edge_t) * (BLOCK_SIZE + 1)); edge_root.sibling = e_next; e_next = edge_root + BLOCK_SIZE; ) --e_next; e_next->nd = b; e_next->len = d; e_next ->irmão = a->edge; a->edge = e_next; ) void free_edges() ( for (; edge_root; edge_root = e_next) ( e_next = edge_root.sibling; free(edge_root); ) ) /* --- fila de prioridade stuff --- */ heap_t *heap; int heap_len; void set_dist(node_t *nd, node_t *via, double d) ( int i, j; /* já conhecia o caminho melhor */ if (nd->via && d >= nd->dist) return; /* encontra uma entrada de heap existente ou cria uma nova */ nd->dist = d; nd->via = via; i = nd->heap_idx; if (!i) i = ++heap_len; /* upheap */ for (; i > 1 && nd->dist< heap->dist; i = j) (heap[i] = heap[j])->heap_idx = i; heap[i] = nd; nd->heap_idx = i; ) node_t * pop_queue() ( node_t *nd, *tmp; int i, j; if (!heap_len) return 0; /* remove o elemento inicial, puxa o elemento final para lá e para baixo */ nd = heap; tmp = heap; for (i = 1; e< heap_len && (j = i * 2) <= heap_len; i = j) { if (j < heap_len && heap[j]->dist > heap->dist) j++; if (heap[j]->dist >= tmp->dist) break; (heap[i] = heap[j])->heap_idx = i; ) heap[i] = tmp; tmp->heap_idx = i; retornar nd; ) /* --- Coisas de Dijkstra; nós inacessíveis nunca entrarão na fila --- */ void calc_all(node_t *start) ( node_t *lead; edge_t *e; set_dist(start, start, 0); while ((lead = pop_queue())) for ( e = lead->edge; e; e = e->irmão) set_dist(e->nd, lead, lead->dist + e->len); ) void show_path(node_t *nd) ( if (nd-> via == nd) printf("%s", nd->name); else if (!nd->via) printf("%s(unreached)", nd->name); else ( show_path(nd-> via); printf("-> %s(%g) ", nd->nome, nd->dist); ) ) int main(void) ( #ifndef BIG_EXAMPLE int i; # define N_NODES ("f" - " a" + 1) node_t *nodes = calloc(sizeof(node_t), N_NODES); for (i = 0; i< N_NODES; i++) sprintf(nodes[i].name, "%c", "a" + i); # define E(a, b, c) add_edge(nodes + (a - "a"), nodes + (b - "a"), c) E("a", "b", 7); E("a", "c", 9); E("a", "f", 14); E("b", "c", 10);E("b", "d", 15);E("c", "d", 11); E("c", "f", 2); E("d", "e", 6); E("e", "f", 9); # undef E #else /* BIG_EXAMPLE */ int i, j, c; # define N_NODES 4000 node_t *nodes = calloc(sizeof(node_t), N_NODES); for (i = 0; i < N_NODES; i++) sprintf(nodes[i].name, "%d", i + 1); /* given any pair of nodes, there"s about 50% chance they are not connected; if connected, the cost is randomly chosen between 0 and 49 (inclusive! see output for consequences) */ for (i = 0; i < N_NODES; i++) { for (j = 0; j < N_NODES; j++) { /* majority of runtime is actually spent here */ if (i == j) continue; c = rand() % 100; if (c < 50) continue; add_edge(nodes + i, nodes + j, c - 50); } } #endif heap = calloc(sizeof(heap_t), N_NODES + 1); heap_len = 0; calc_all(nodes); for (i = 0; i < N_NODES; i++) { show_path(nodes + i); putchar("\n"); } #if 0 /* real programmers don"t free memories (they use Fortran) */ free_edges(); free(heap); free(nodes); #endif return 0; }

    PHP

    $edge, "custo" => $edge); $vizinhos[$edge] = array("fim" => $edge, "custo" => $edge); ) $vértices = array_unique($vértices); foreach ($vertices as $vertex) ( $dist[$vertex] = INF; $previous[$vertex] = NULL; ) $dist[$source] = 0; $Q = $vértices; while (count($Q) > 0) ( // TODO - Encontre uma maneira mais rápida de obter o mínimo $min = INF; foreach ($Q as $vertex)( if ($dist[$vertex]< $min) { $min = $dist[$vertex]; $u = $vertex; } } $Q = array_diff($Q, array($u)); if ($dist[$u] == INF or $u == $target) { break; } if (isset($neighbours[$u])) { foreach ($neighbours[$u] as $arr) { $alt = $dist[$u] + $arr["cost"]; if ($alt < $dist[$arr["end"]]) { $dist[$arr["end"]] = $alt; $previous[$arr["end"]] = $u; } } } } $path = array(); $u = $target; while (isset($previous[$u])) { array_unshift($path, $u); $u = $previous[$u]; } array_unshift($path, $u); return $path; } $graph_array = array(array("a", "b", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9)); $path = dijkstra($graph_array, "a", "e"); echo "path is: ".implode(", ", $path)."\n";


    Pitão

    from collections import namedtuple, queue from pprint import pprint as pp inf = float("inf") Edge = namedtuple("Edge", "start, end, cost") class Graph(): def __init__(self, edge): self .edges = edge2 = self.vertices = set(sum(( para e em edge2), )) def dijkstra(self, source, dest): assert source in self.vertices dist = (vertex: inf para vértice em self.vertices ) anterior = (vértice: Nenhum para vértice em self.vertices) dist = 0 q = self.vertices.copy() vizinhos = (vértice: set() para vértice em self.vertices) para início, fim, custo em self. arestas: vizinhos.add((fim, custo)) #pp(vizinhos) while q: u = min(q, chave=lambda vértice: dist) q.remove(u) if dist[u] == inf ou u = = dest: pausa para v, custo em vizinhos[u]: alt = dist[u] + custo se alt< dist[v]: # Relax (u,v,a) dist[v] = alt previous[v] = u #pp(previous) s, u = deque(), dest while previous[u]: s.pushleft(u) u = previous[u] s.pushleft(u) return s graph = Graph([("a", "b", 7), ("a", "c", 9), ("a", "f", 14), ("b", "c", 10), ("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6), ("e", "f", 9)]) pp(graph.dijkstra("a", "e")) Output: ["a", "c", "d", "e"]

    Artigos semelhantes