C++ Struktur Wert scheint sich zu ändern

Question

Ich bin nur ein einfacher Code ausgeführt, aber ich bekomme immer "Prozess beendet mit Exit-Code 139 (unterbrochen von Signal 11: SIGSEGV)" Tun einige Debugging, fand ich, dass die Wert der Kanten [0] .start wird irgendwie -2147483644. Ich finde dieses Verhalten ziemlich schwer zu erklären und versuche immer noch herauszufinden, wo ich es falsch verstanden habe, aber ich aktualisiere keine Kantenwerte! Wie auch immer, was immer Sie mir geben können, wird sehr geschätzt. Sie finden den folgenden Code. Vielen Dank im Voraus! warme Wünsche

#include <stdio.h> 
#include <climits> 
#include "Utils.h" 

struct edge { 
    int start; 
    int end; 
    int weight; 
}; 

int main() { 
    int n = 4; 
    int m = 4; 
    edge edges[4] = { 
      {2,4,5}, 
      {4,1,6}, 
      {1,3,8}, 
      {3,2,-3} 
    }; 
    int v,e; 
    int distance[4]; 
    // Step 1: initialize graph 
    for(v = 0; v < n; v++){ 
     distance[v] = INT_MAX; 
    } 
    distance[0] = 0; //source 

    // Step 2: relax edges repeatedly 
    for(v = 0; v < n; v++){ 
     for(e = 0; e < m; e++){ 
      if(distance[edges[e].start] + edges[e].weight < distance[edges[e].end]){ //relax 
       distance[edges[e].end] = distance[edges[e].start] + edges[e].weight; 
      } 
     } 
    } 
    // Step 3: check for negative-weight cycles 
    for(e = 0; e < m; e++) { 
     if (distance[edges[e].start] + edges[e].weight < distance[edges[e].end]) { //shouldn't be able to relax 
      std::cout << "Negative cycle detected, please declare war to Paraguay"; 
     } 
    } 
    for(v = 0; v < n; v++){ 
     std::cout << distance[v] << std::endl; 
    } 
    return 0; 
} 

Answer 1

Sie haben Abstand Variable definiert mit einer Größe von 4

int distance[4]; 

während die Werte der Kantenfeld sind:

edge edges[4] = { 
      {2,4,5}, 
      {4,1,6}, 
      {1,3,8}, 
      {3,2,-3} 
    }; 

Sie verwenden Wert von edge structure die zuzugreifen Zelle von jedem distance array. Der Wert der Kante reicht von -3 bis 8, während der Wert der Entfernung von 0 bis 3 reicht; Dies führt zu einem Pufferüberlauf und führt zum Absturz der Anwendung.

Answer 2

Ich bin eigentlich weiß nicht, warum, aber das funktioniert für mich:

#include <iostream> 

struct edge { 
    int start; 
    int end; 
    int weight; 
}; 

int main() { 
    int n = 4; 
    int m = 4; 

    const edge edges[4] = { 
      {2,4,5}, 
      {4,1,6}, 
      {1,3,8}, 
      {3,2,-3} 
    }; /* <= for my surprise, I'm not get error with this 
     * for indexes of distance[something] 
     */ 
    int v,e; 
    int distance[4]; 
    // Step 1: initialize graph 
    for(v = 0; v < n; v++){ 
     distance[v] = 214748364; // <== with this get fixed 
    } 
    distance[0] = 0; //source 

    // Step 2: relax edges repeatedly 
     for(v = 0; v < n; v++){ 
      for(e = 0; e < m; e++){ 
       if(distance[edges[e].start] + edges[e].weight < distance[edges[e].end]){ //relax 
        distance[edges[e].end] = distance[edges[e].start] + edges[e].weight; 
       } 
      } 
     } 
     // Step 3: check for negative-weight cycles 
     for(e = 0; e < m; e++) { 
      if (distance[edges[e].start] + edges[e].weight < distance[edges[e].end]) { //shouldn't be able to relax 
       std::cout << "Negative cycle detected, please declare war to Paraguay"; 
      } 
     } 
     for(v = 0; v < n; v++){ 
      std::cout << distance[v] << std::endl; 
     } 
    return 0; 
} 

Statt Verwendung distance[v] = INT_MAX; einfach verwenden distance[v] = 214748364; oder etwas nicht so nahe von INT_MAX und ich diese Ausgabe:

0 
8 
13 
16 
Press <RETURN> to close this window... 

Answer 3

Ihre 'n' und 'm' Iteratorvariablen sind als 4 definiert, doch das 'Kanten' Array hat Indizes zwischen 0 und einschließlich 3. Ihre Schleife wird versuchen, auf Kanten [4] zuzugreifen, was zu einem Index außerhalb des Bereichs und zu undefiniertem Verhalten führt, was wahrscheinlich die Ursache für Ihre Startwertkorruption ist.