Я пытаюсь реализовать алгоритм кратчайшего пути Дейкстры. Для этого я создал список смежности для представления графика, и он дает правильный вывод, но проблема заключается в том, что всякий раз, когда я пытаюсь объявить массив с помощью distance_array_new[(graph -> no_vertices)]
, он дает ошибку, также когда я пытаюсь изменить значения массива. Я даже не могу проверить указатель на NULL
, он выдает ошибку.
Я пытался проверить указатель на NULL
.
Я пытался проверить, используя цифры. например, 5, 6.
Ничего не сработало.
#include <stdio.h>
#include <stdlib.h>
/* The graph vertices are labeled as 1,2,3,4,5 but represented as 0,1,2,3,4 */
typedef struct ListNode{
int vertex_number;
int weight;
struct ListNode* next;
}Node;
typedef struct Graph {
int no_vertices;
int source;
int total_weight;
Node* list;
}Graph;
Graph* initialize_graph(FILE *fnodes, Graph *graph) {
int total_vertex, source;
fscanf(fnodes, "%d,%d", &total_vertex, &source);
graph -> no_vertices = total_vertex;
graph -> source = source;
graph -> list = (Node*)malloc(sizeof(Node) * (graph->no_vertices));
return graph;
}
Node* adjacency_list(FILE *fnodes, Graph * graph) {
int total_weight=0, start, end, weight;
Node *temp;
Node *trav = graph -> list;
// Preprocessing of the adjacency list
for (int i = 0; i < graph->no_vertices; ++i)
{
graph -> list[i].vertex_number = i; // to represent each vertex
graph -> list[i].next = NULL;
}
while(fscanf(fnodes, "%d,%d,%d", &start, &end, &weight) == 3) {
temp = (Node *)malloc(sizeof(Node));
temp -> vertex_number = end;
temp -> next = NULL;
temp -> weight = weight;
trav = &(graph -> list[start - 1]);
while(trav -> next != NULL) {
trav = trav -> next;
}
trav -> next = temp;
total_weight += weight;
}
graph -> total_weight = total_weight;
return graph -> list;
}
void print(Graph *graph) {
Node* trav = graph -> list;
for (int i = 0; i < graph -> no_vertices; ++i)
{
trav = &(graph -> list[i]);
printf("Vertex no. : %d ", graph -> list[i].vertex_number);
while (trav -> next != NULL) {
printf("DEST : %d \n", trav -> next -> vertex_number);
trav = trav -> next;
}
}
printf("\n");
}
int main() {
FILE *fnodes = fopen("nodes.txt", "r");
Graph *graph;
graph = initialize_graph(fnodes, graph);
printf("Details of graph, Nodes and Source: %d %d\n", graph->no_vertices, graph->source);
printf("--Adjacency List--(Started from Vertex number 0)\n");
graph -> list = adjacency_list(fnodes, graph);
printf("Total Weight: %d\n", graph -> total_weight);
print(graph);
int distance_array_new[graph -> no_vertices]; //failed
int *distance_array;
distance_array = (int *)malloc(sizeof(int) * (graph -> no_vertices));
if (distance_array == NULL) {
printf("NO MEMORY\n");
}
/* NOTE: If I try to initialize the array normally, or read it's contents in a for loop,
or try to change the value, check the pointer it gives a Seg fault and I don't know Why.
Uncomment below code and Run */
printf("V: %d\n", distance_array[0]);
for (int i = 0; i < (graph -> no_vertices); i++)
{
distance_array[i] = (graph -> total_weight) + 15;
}
distance_array[(graph -> source) - 1] = 0; //Initial distance is 0 for source.
}
nodes.txt
5,1
1,4,25
1,2,45
2,4,20
3,2,18
4,3,19
4,5,11
3,5,17