@evgeniy666pnd

Почему постоянно выводится расстояние 0(Алгоритм Дейкстры для городов)?

Постоянно выводится расстояние равное 0, хотя кратчайший путь ищется правильно. В файле graph.txt данные в таком формате:
Moscow Saintpetersburg 700
Saintpetersburg Novgorod 400
Moscow Novosibirsk 3000
Novgorod Volgograd 1200
Volgograd Sochi 900
Выводится вот что:
6626790064cc6077809228.png
Код представлен ниже. Буду счастлив, если кто-то объяснить в чем я туплю.
#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(" -> ");
    }
}
  • Вопрос задан
  • 949 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Вы выводите d[begin_index], это расстояние до начальной вершины. Естественно там 0 будет. А выводить надо расстояние до конечной. Надо end использовать (и выводить после того, как вы end нашли).
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы