Vou dar um exemplo de uma matriz:
Obs.: Essa matriz é um exemplo, pois o usuário pode definir o tamanho da matriz e preenche-la.
1 2 3 4 5
1 | 00 | 23 | 11 | 36 | 00 |
2 | 23 | 00 | 44 | 25 | 78 |
3 | 11 | 44 | 00 | 37 | 13 |
4 | 36 | 25 | 37 | 00 | 07 |
5 | 00 | 78 | 13 | 07 | 00 |
3 Regrinhas do Algoritmo.
1º - E se a linha e a coluna receberem um valor, quando eles serem ao contraria receberá o mesmo valor.
Ex.:
[linha1][coluna4]=36;
[linha4][coluna1]=36;
ou
[linha3][coluna5]=13;
[linha5][coluna3]=13;
E assim sucessivamente.
2º - Quando a linha e coluna forem diferentes é tiverem recebido o valor zero, quer dizer que o valor(a distancia de uma cidade para outra no caso do algoritmo) é nulo e será feito o processo do algoritmo de dijkstra.
3º - Quando a linha e a coluna da matriz forem as mesmas o valor recebido é zero.
Ex.:
[linha1][coluna1]=00;
[linha2][coluna2]=00;
E por ai vai.
Especificação de que o algoritmo deve fazer:
O usuário ira escolher o tamanho da matriz.
• Obs.: Esta definido no meu algoritmo como cidades a linha e coluna(linha é igual ao mesmo numero de colunas).
O usuário após ter escolhido o tamanho da matriz ira preenche-la. Existem 3 regrinhas para preencher a matriz.(está apresentado anteriormente neste tópico).
Após preencher a matriz o usuário ira escolher uma linha e uma coluna(que é cidade de origem até a cidade de destino).
Se a linha e coluna tiver o valor maior que zero( quer dizer que tem distancia) e será exibido para o usuário.
Se a linha e coluna escolhidas forem a mesma(no caso se a cidade de origem for igual a cidade de destino) retorna para o usuário que as cidades escolhidas são a mesma.
O usuário escolheu a linha 1 e coluna 5(cidade de origem 1 e a cidade de destino 5), se o valor da linha 1 e coluna 5 for 0(a distancia entre a cidade 1 a cidade 5 é zero, quer dizer que não tem distancia), o algoritmo deverá procurar na linha escolhida(ou seja a cidade de origem) qual é o menor valor na coluna existente nela(quer dizer que ira procurar distancia da cidade 1 para outra cidade que seja menor).==Processo que sera feito é o Algoritmo de Dijkstra.
• Após encontrado o menor valor na linha(cidade de origem, no caso foi escolhida a 1) que esta na coluna 3(cidade 3), o algoritmo devera pular para a linha 3(cidade 3) e verificar se tem caminho direto pra coluna escolhida anteriormente(no caso coluna 5(cidade 5)) e somar os valores encontrados
Ex.: linha[1] coluna[3]=11;
linha[3] coluna[5]=13;
somaLinhaColuna=24;
• E retornar para o usuário que a distancia menor para chegar da cidade 1(linha 1) para a cidade 5(coluna 5) é 24, mas para obter essa distancia(valor) ele deverá passar para a cidade 3(linha 3).
A duvida é:
- Como fazer o algoritmo pular de linha de acordo com a coluna em que ele encontrou o menor valor??
Obs.: Essa matriz é um exemplo, pois o usuário pode definir o tamanho da matriz e preenche-la.
1 2 3 4 5
1 | 00 | 23 | 11 | 36 | 00 |
2 | 23 | 00 | 44 | 25 | 78 |
3 | 11 | 44 | 00 | 37 | 13 |
4 | 36 | 25 | 37 | 00 | 07 |
5 | 00 | 78 | 13 | 07 | 00 |
3 Regrinhas do Algoritmo.
1º - E se a linha e a coluna receberem um valor, quando eles serem ao contraria receberá o mesmo valor.
Ex.:
[linha1][coluna4]=36;
[linha4][coluna1]=36;
ou
[linha3][coluna5]=13;
[linha5][coluna3]=13;
E assim sucessivamente.
2º - Quando a linha e coluna forem diferentes é tiverem recebido o valor zero, quer dizer que o valor(a distancia de uma cidade para outra no caso do algoritmo) é nulo e será feito o processo do algoritmo de dijkstra.
3º - Quando a linha e a coluna da matriz forem as mesmas o valor recebido é zero.
Ex.:
[linha1][coluna1]=00;
[linha2][coluna2]=00;
E por ai vai.
Especificação de que o algoritmo deve fazer:
O usuário ira escolher o tamanho da matriz.
• Obs.: Esta definido no meu algoritmo como cidades a linha e coluna(linha é igual ao mesmo numero de colunas).
O usuário após ter escolhido o tamanho da matriz ira preenche-la. Existem 3 regrinhas para preencher a matriz.(está apresentado anteriormente neste tópico).
Após preencher a matriz o usuário ira escolher uma linha e uma coluna(que é cidade de origem até a cidade de destino).
Se a linha e coluna tiver o valor maior que zero( quer dizer que tem distancia) e será exibido para o usuário.
Se a linha e coluna escolhidas forem a mesma(no caso se a cidade de origem for igual a cidade de destino) retorna para o usuário que as cidades escolhidas são a mesma.
O usuário escolheu a linha 1 e coluna 5(cidade de origem 1 e a cidade de destino 5), se o valor da linha 1 e coluna 5 for 0(a distancia entre a cidade 1 a cidade 5 é zero, quer dizer que não tem distancia), o algoritmo deverá procurar na linha escolhida(ou seja a cidade de origem) qual é o menor valor na coluna existente nela(quer dizer que ira procurar distancia da cidade 1 para outra cidade que seja menor).==Processo que sera feito é o Algoritmo de Dijkstra.
• Após encontrado o menor valor na linha(cidade de origem, no caso foi escolhida a 1) que esta na coluna 3(cidade 3), o algoritmo devera pular para a linha 3(cidade 3) e verificar se tem caminho direto pra coluna escolhida anteriormente(no caso coluna 5(cidade 5)) e somar os valores encontrados
Ex.: linha[1] coluna[3]=11;
linha[3] coluna[5]=13;
somaLinhaColuna=24;
• E retornar para o usuário que a distancia menor para chegar da cidade 1(linha 1) para a cidade 5(coluna 5) é 24, mas para obter essa distancia(valor) ele deverá passar para a cidade 3(linha 3).
A duvida é:
- Como fazer o algoritmo pular de linha de acordo com a coluna em que ele encontrou o menor valor??