This program was working fine when i was declaring 2-D array
weight[10000][10000]
as a global variable but with lower size But now i am passing that array toaddedege()
anddijkstra()
function Please can you tell me where is the error in passing a 2-D array When i give breakpoint at starting starting of main not a single line was executing incodeblocks
and there was no warning no error while compilation And invisual studio
it is saying thatUnhandled exception at 0x00A31979 in Project6.exe: 0xC00000FD: Stack overflow (parameters: 0x00000000, 0x1AE42000).
Please tell me what proper of declaring a large 2-d array because when i was declaring in Global section it is saying that array too large with smaller size no problem program working fine
this was the question on hackerrankhttps://www.hackerrank.com/challenges/dijkstrashortreach/problem
#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
// Node
typedef struct node {
int data;
// Lower values indicate higher priority
int priority;
struct node* next;
} Node;
// Function to Create A New Node
Node* newNode(int d, int p)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = d;
temp->priority = p;
temp->next = NULL;
return temp;
}
// Return the value at head
int peek(Node** head)
{
return (*head)->data;
}
// Removes the element with the
// highest priority form the list
void pop(Node** head)
{
Node* temp = *head;
(*head) = (*head)->next;
free(temp);
}
void updateprt(Node** head, int data) {
Node* start = *head;
while (start->data != data) {
start = start->next;
}
Node* current = start->next;
start->next = current->next;
free(current);
}
// Function to push according to priority
void push(Node** head, int d, int p)
{
Node* start = (*head);
// Create new Node
Node* temp = newNode(d, p);
if (*head == NULL) {
*head = temp;
return;
}
// Special Case: The head of list has lesser
// priority than new node. So insert new
// node before head node and change head node.
if ((*head)->priority > p) {
// Insert New Node before head
temp->next = *head;
(*head) = temp;
}
else {
// Traverse the list and find a
// position to insert new node
while (start->next != NULL &&
start->next->priority < p) {
start = start->next;
}
// Either at the ends of the list
// or at required position
temp->next = start->next;
start->next = temp;
}
}
// Function to check is list is empty
int isEmpty(Node** head)
{
return (*head) == NULL;
}
struct adjlistnode {
int data;
struct adjlistnode* next;
};
struct adjlist {
struct adjlistnode* head;
};
struct graph {
int v;
struct adjlist* array;
};
struct graph* creategraph(int v) {
struct graph* G = (struct graph*) malloc(sizeof(struct graph));
G->v = v;
int i;
G->array = (struct adjlist*)malloc(sizeof(struct adjlist)*v);
for (i = 0; i < v; i++) {
G->array[i].head = NULL;
}
return G;
}
int Distance[100000], path[50];
struct adjlistnode* getnewnode(int ver) {
struct adjlistnode* newnode = (struct adjlistnode*)malloc(sizeof(struct adjlistnode));
newnode->data = ver;
newnode->next = NULL;
return newnode;
}
void addedge(struct graph* G, int src, int dest, long int w, int weight[][10000]) {
struct adjlistnode* temp;
temp = getnewnode(dest);
temp->next = G->array[src].head;
G->array[src].head = temp;
temp = getnewnode(src);
temp->next = G->array[dest].head;
G->array[dest].head = temp;
weight[src][dest] = w;
weight[dest][src] = w;
}
void printgraph(struct graph* G) {
for (int i = 0; i < G->v; i++) {
struct adjlistnode* temp = G->array[i].head;
printf("%d-> ", i);
while (temp) {
printf(" %d", temp->data);
temp = temp->next;
}
printf("\n");
}
}
void Dijkstra(Node** queue, struct graph* G, int s, int weight[][10000]) {
int v, w, d;
push(queue, s, 0);
for (int i = 0; i < 100000; i++) {
Distance[i] = -1;
}
Distance[s] = 0;
while (!isEmpty(queue)) {
v = peek(queue);
pop(queue);
struct adjlistnode* temp = G->array[v].head;
while (temp) {
w = temp->data;
d = Distance[v] + weight[v][w];
//To update the distance of w check the below two conditions
if (Distance[w] == -1) {
Distance[w] = d;
push(queue, w, d);
path[w] = v;
}
if (Distance[w] > d)
{
Distance[w] = d;
path[w] = v;
updateprt(queue, w);
push(queue, w, d);
}
temp = temp->next;
}
}
}
int main()
{
int t;
scanf("%d", &t);
while (t) {
int weight[10000][10000];
Node* pq = NULL;
int v;
int e;
scanf("%d %d", &v, &e);
struct graph* G = creategraph(v);
int u, w;
int l;
for (int i = 0; i < e; i++) {
scanf("%d %d %ld", &u, &w, &l);
addedge(G, u - 1, w - 1, l, weight);
}
int s;
scanf("%d", &s);
Dijkstra(&pq, G, s - 1, weight);
for (int i = 0; i < G->v; i++) {
if (i == s - 1)
continue;
printf("%d ", Distance[i]);
}
printf("\n");
t--;
}
}
In visual studio, default stack size is 1 MB. Now, however it is not so recommended, but if you need so, you can increase it by using the /F switch. However, increasing the stack size brought some other unforeseen situation in my project and had to re-design the code but I think, this solution will work for your problem
A stack overflow is an undesirable condition in which a particular computer program tries to use more memory space than the call stack has available. In programming, the call stack is a buffer that stores requests that need to be handled.
Your weight
array is occupying more memory.
Alternatively, you could dynamically allocate the memory for your 2d array, as the heap is bigger than the stack. Thus int weight[10000][10000]
will become int(*weight)[10000] = malloc(sizeof(int[10000][10000]));
. Don't forget to free(weight);
when you're done.
User contributions licensed under CC BY-SA 3.0