Olá Fabio! A estruturação da sua rede é o que irá determinar as vias possíveis e excluir aquelas que são contramão, sendo uma etapa prévia ao que é apresentado. No vídeo abordamos a heurística de Clarke e Wright (1964) como método para otimizar a programação de rotas em uma rede simples e pré-determinada. Caso no caminho (link entre origem e destino) houvesse uma via de mão única mudaríamos o caminho para outro possível, o que iria alterar a distância, podendo posteriormente impactar a programação de rotas. A rede foi definida como um grafo simples, aonde se v-w é um arco então w-v também é um arco. Para tratar a situação da sua pergunta precisaríamos de um dígrafo (ou grafo orientado).

@@MarlonFernandesdeSouza Muito obrigado pela orientação, vou buscar estudar sobre o grafo orientado. Já me deu um norte para continuar.

Lembrando que tanto a estruturação da rede quanto o path-finding (Problema do menor caminho) que aparecem no artigo do Medium são etapas prévias ao que fizemos no vídeo (organizar a melhor sequencia de paradas na rota). Partimos do pressuposto que as distâncias apresentadas representavam os menores caminhos possíveis entre as cidades. O Google Maps, por exemplo, é um aplicativo de path-finding. Vc até consegue ir adicionando paradas à sua rota, mas ele sugere o melhor caminho entre as paradas na sequência que vc inseriu, e não uma mudança na ordem entre as paradas para ter uma rota otimizada, que é o que fizemos no exemplo.

Nesse exemplo, por simplicidade, ela considerou que a distância ab = distância ba. Mas, aplicando num caso mais real, na hora de montar a matriz com todas as distâncias, leva-se em conta essa diferença entre ir do ponto a ao ponto b e ir de b ao ponto a. Feito isso, segue o passo a passo do algoritimo, calculando as economias e listando-as em ordem decrescente (aqui, vão existir duas economias distintas Sab e Sba).

@@vinidasexatas6019 nesse caso serão montadas duas matrizes? Pois cada lacuna matriz permite apenas um valor para alocar. A sua ideia é interessante mas não entendi como funcionaria.

@@FabioSilva-ek3ox sim. Ela fez algo não muito usual de unir a matriz de distâncias com a de economias. Só é possível fazer isso nesse caso mais simples de considerar Distancia ab = Distancia ba. Num caso mais real, teria uma matriz para distâncias e uma separada para economias. Fica até mais fácil de programar assim.

@@vinidasexatas6019 A duvida que fico é como colocar esses dados para o algoritmo, ja que o mesmo nao faz distinção de a-b ou b-a. O algoritmo é bem simples.