Постоянно выводится расстояние равное 0, хотя кратчайший путь ищется правильно. В файле graph.txt данные в таком формате:
Moscow Saintpetersburg 700
Saintpetersburg Novgorod 400
Moscow Novosibirsk 3000
Novgorod Volgograd 1200
Volgograd Sochi 900
Выводится вот что:
Код представлен ниже. Буду счастлив, если кто-то объяснить в чем я туплю.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <stdbool.h>
#define MAX_VERTICES 50
#define MAX_EDGES 50
struct Edge {
char vertex1[50];
char vertex2[50];
int distance;
};
void ReadEdgesFromFile(FILE* file, struct Edge* edges, int* numEdges, char vertices[][50], int* numVertices);
void DijkstraAlgorithm(struct Edge* edges, int numEdges, char vertices[][50], int numVertices, char* startVertex, char* endVertex);
int main() {
FILE* fp = NULL;
int numEdges = 0;
int numVertices = 0;
char startVertex[50], endVertex[50];
char vertices[MAX_VERTICES][50];
printf("Enter the start vertex: ");
if (scanf("%s", startVertex) != 1) {
printf("Error: Invalid start vertex input.\n");
return 1;
}
printf("Enter the end vertex: ");
if (scanf("%s", endVertex) != 1) {
printf("Error: Invalid end vertex input.\n");
return 1;
}
// Open the file containing graph data
if ((fp = fopen("graph.txt", "r")) == NULL) {
printf("Failed to open the file.\n");
return 1;
}
// Read the edge data from the file
struct Edge* edges = (struct Edge*)malloc(MAX_EDGES * sizeof(struct Edge));
if (edges == NULL) {
printf("Failed to allocate memory for the array of edges.\n");
fclose(fp);
return 1;
}
// Read the vertices and edges from file
ReadEdgesFromFile(fp, edges, &numEdges, vertices, &numVertices);
// Close the file
fclose(fp);
// Output the read edges (for debugging purposes)
printf("Edges read from file:\n");
for (int i = 0; i < numEdges; ++i) {
printf("Edge: %s - %s, Distance: %d\n", edges[i].vertex1, edges[i].vertex2, edges[i].distance);
}
// Apply Dijkstra's algorithm
DijkstraAlgorithm(edges, numEdges, vertices, numVertices, startVertex, endVertex);
// Free the memory allocated for the array of edges
free(edges);
return 0;
}
// Function to read the graph edges from a file
void ReadEdgesFromFile(FILE* file, struct Edge* edges, int* numEdges, char vertices[][50], int* numVertices) {
while (fscanf(file, " %s %s %d", edges[*numEdges].vertex1, edges[*numEdges].vertex2, &edges[*numEdges].distance) == 3) {
// Add vertices to the vertex array if not already present
bool foundVertex1 = false;
bool foundVertex2 = false;
for (int i = 0; i < *numVertices; ++i) {
if (strcmp(vertices[i], edges[*numEdges].vertex1) == 0) {
foundVertex1 = true;
}
if (strcmp(vertices[i], edges[*numEdges].vertex2) == 0) {
foundVertex2 = true;
}
}
if (!foundVertex1) {
strcpy(vertices[*numVertices], edges[*numEdges].vertex1);
(*numVertices)++;
}
if (!foundVertex2) {
strcpy(vertices[*numVertices], edges[*numEdges].vertex2);
(*numVertices)++;
}
// Move to the next edge
(*numEdges)++;
}
}
// Function implementing Dijkstra's algorithm
void DijkstraAlgorithm(struct Edge* edges, int numEdges, char vertices[][50], int numVertices, char* startVertex, char* endVertex) {
int SIZE = numVertices;
int a[MAX_VERTICES][MAX_VERTICES] = { 0 }; // Adjacency matrix to represent the graph
int begin_index = 0; // Start vertex index
int temp, minindex, min;// Variable to store the index of the minimum distance vertex
int d[MAX_VERTICES]; // Array to store distances to vertices
bool visited[MAX_VERTICES]; // Array to track visited vertices
// Create a mapping from vertex names to indices
int vertexIndices[MAX_VERTICES];
for (int i = 0; i < numVertices; ++i) {
if (strcmp(vertices[i], startVertex) == 0) {
begin_index = i;
}
vertexIndices[i] = i;
}
// Populate adjacency matrix using the provided edges
for (int i = 0; i < numEdges; ++i) {
int index1 = -1, index2 = -1;
for (int j = 0; j < numVertices; ++j) {
if (strcmp(edges[i].vertex1, vertices[j]) == 0)
index1 = j;
if (strcmp(edges[i].vertex2, vertices[j]) == 0)
index2 = j;
}
if (index1 != -1 && index2 != -1) {
a[index1][index2] = edges[i].distance;
a[index2][index1] = edges[i].distance; // Assuming undirected graph
}
}
//Инициализация вершин и расстояний
for (int i = 0; i < SIZE; i++) {
d[i] = 10000;
visited[i] = false;
}
d[begin_index] = 0;
// Dijkstra's algorithm steps
do {
minindex = INT_MAX;
min = INT_MAX;
// Find the vertex with the minimum distance
for (int i = 0; i < SIZE; i++) {
if (!visited[i] && d[i] < min) {
min = d[i];
minindex = i;
}
}
// If a vertex for processing is found
if (minindex != INT_MAX) {
visited[minindex] = true;
for (int i = 0; i < SIZE; i++) {
if (a[minindex][i] > 0) {
temp = min + a[minindex][i];
if (temp < d[i]) {
d[i] = temp;
}
}
}
}
} while (minindex < INT_MAX);
// Output shortest distances to vertices
printf("\nShortest distance from %s to %s: %d\n", startVertex, endVertex, d[begin_index]);
// Path restoration
int ver[MAX_VERTICES]; // Array of visited vertices
int end = -1; // Index of the end vertex
for (int i = 0; i < numVertices; ++i) {
if (strcmp(vertices[i], endVertex) == 0) {
end = i;
break;
}
}
if (end == -1) {
printf("End vertex not found in graph.\n");
return;
}
ver[0] = end; // Initial element is the end vertex
int k = 1; // Index of the previous vertex
int weight = d[end]; // Weight of the end vertex
while (end != begin_index) { // While not reached the starting vertex
for (int i = 0; i < SIZE; i++) { // Traverse all vertices
if (a[i][end] != 0) { // If there is a connection
int temp = weight - a[i][end]; // Determine the weight of the path from the previous vertex
if (temp == d[i]) { // If the weight matches the calculated one
weight = temp; // Save the new weight
end = i; // Save the previous vertex
ver[k] = i; // And write it to the array
k++;
break; // Break the loop once the previous vertex is found
}
}
}
}
// Output the path
printf("Shortest path from %s to %s: ", startVertex, endVertex);
for (int i = k - 1; i >= 0; i--) {
printf("%s", vertices[ver[i]]);
if (i > 0)
printf(" -> ");
}
}
Простой
