Алгоритм Дейкстры для городов

[NikitaPND]

Постоянно пишет что расстояние равно 0, хотя путь находит правильно, не знаю что еще поменять.

#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(" -> ");
    }
}

[ViktorR]

Вот фрагмент вашего кода:

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]);

И что должно выводиться по вашему?