I am new around here. I study Computer Engineering 1st, and I use C++ in Fundamentals of Programming.
Well, I am solving this exercise (I put it as an image because it is quite confusing):
My code is the following:
#include <iostream>
#include <locale>
#include <cstdlib>
using namespace std;
const int NCIUDADES = 8;
void hazRuta(const int kilometros [][NCIUDADES], int ciudadActual, int ruta[]){
bool visitados [NCIUDADES];
for (int j = 0; j < NCIUDADES; j++)
visitados[j] = false;
int distanciaMenor, ciudadDMenor, contadorRuta = 0;
while (contadorRuta < NCIUDADES){
distanciaMenor = kilometros[0][ciudadActual];
for (int i = 0; i < NCIUDADES; i++){
if (i == ciudadActual)
continue;
if (kilometros[i][ciudadActual] < distanciaMenor && visitados[i] == false){
distanciaMenor = kilometros[i][ciudadActual];
ciudadDMenor = i;
}
}
ruta[contadorRuta] = ciudadDMenor;
contadorRuta++;
visitados[ciudadDMenor] = true;
ciudadActual = ciudadDMenor;
}
}
int main (){
setlocale(LC_ALL, "Spanish");
//Ciudades: 0-Almería, 1-Cádiz, 2-Córdoba, 3-Granada, 4-Huelva, 5-Jaén, 6-Málaga y 7-Sevilla
int kilometros [NCIUDADES][NCIUDADES] = {{0, 615, 364, 166, 608, 283, 210, 503},{615, 0, 268, 347, 248, 360, 268, 145},{364, 268, 0, 200, 236, 105, 172, 133}
,{166, 347, 200, 0, 373, 91, 164, 269},{608, 248, 236, 373, 0, 335, 318, 96},{283, 360, 105, 91, 335, 0, 236, 234}
,{210, 268, 172, 164, 318, 236, 0, 215},{503, 145, 133, 269, 96, 234, 215, 0}};
int partida, ruta [NCIUDADES];
cout << "Introduzca el número de la ciudad de partida (0-Almería, 1-Cádiz, 2-Córdoba, 3-Granada, 4-Huelva, 5-Jaén, 6-Málaga y 7-Sevilla): ";
cin >> partida;
while (partida < 0 || partida > 7){
cout << "Número no válido. Reintrodúzcalo: ";
cin >> partida;
}
hazRuta(kilometros, partida, ruta);
cout << "La ruta para visitar todas las ciudades es: ";
for (int i = 0; i < NCIUDADES; i++){
cout << ruta[i] << ", ";
}
cout << endl;
system("Pause");
return 0;
}
To begin with, if I choose 0 as the starting city, the "Segmentation Fault" error occurs, something that has happened to me once when working with pointers, but that I don't understand in a simple fixed-size array.
On the other hand, if I choose another city as a starting point, the program runs, but the result is clearly incorrect. For example, for city 6 I receive the result:
3, 5, 2, 7, 4, 1, 6, 6
It is probably absurd, but I am unable to find the error.
I appreciate any help, but please keep in mind that I'm just getting started in this area.
Thank you very much. All the best.
The problem for city 0
In your function
hazRuta()
you have this line:That is, you initialize
distanciaMenor
as the distance between city 0 and the current city. But if the current city is city 0, the distance will be 0! Therefore no other city is going to achieve a better distance! So itciudadMenor
is left uninitialized and when you later try to dovisitados[ciudadMenor] = true
, you already have a segfault since itciudadMenor
can have any arbitrary value.It doesn't produce a segmentation fault for me, because my compiler initializes the variables to 0 by default, so that it
ciudadMenor
remains with the value 0 when exiting the loop. But this doesn't fix the problem either, since it will choose city 0 as the city to travel to, and it will repeat the loop starting again from that same city. So it generates the "optimal path" 0, 0, 0, 0, 0... until itcontadorRuta
reaches the valueNCIUDADES
and then it stops iterating.Possible solution
You can initialize
distanciaMenor
with an arbitrarily large value, which is greater than the distance to any other city, such as the constantINT_MAX
(default inlimits.h
). Or, as Trauma mentions in a comment, by valuestd::numeric_limits< int >::max( );
(requires#include <limits>
). Or if you prefer, define a constantMAX_DISTANCIA
and give it a large value like 10000 (greater than any of the distances in the matrix).Other cities
The aforementioned bug affects any other starting city as soon as the route reaches city 0, since in that case it
distanciaMenor
is again zero, unbeatable, and is not updatedciudadMenor
, which therefore maintains the value it had in the previous iteration of the loop. That is why city 6 is repeated at the end, when the route should end in city 0.Once the previous correction has been made, it gives me the route:
Answering your question: 1. The segmentation fault is because distanceMinor is initialized with Kilometers[0][CurrentCity] and if CityCurrent is 0, then DistanceMinor will always be 0, therefore, CityDMinor (which is not initialized) will be used as an index in visited[CiudadDMenor]. To correct this, change the line: MinorDistance=kilometers[0][CurrentCity] to MinorDistance=999999;
Your program would look like this:
}