Skip to content
The Chat Archive
gpt-4o-2024-05-13· OpenAI WildChat-4.8M (AI2)

bellman-ford 알고리즘을 활용해서 adjacency list로 구현된 그래프를 순회해서 shortest path를 찾아서 path의 경로를 출력하고…

  1. User

    bellman-ford 알고리즘을 활용해서 adjacency list로 구현된 그래프를 순회해서 shortest path를 찾아서 path의 경로를 출력하고 그 cost를 출력하는 함수를 C언어로

  2. Assistant

    Bellman-Ford 알고리즘은 그래프에서 주어진 시작점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 음의 가중치를 갖는 간선이 존재하는 경우에도 동작합니다. 하지만 음의 사이클(negative cycle)이 존재할 경우 이를 감지하여 알려줍니다.

    아래는 C 언어로 Bellman-Ford 알고리즘을 구현한 코드입니다. 이 코드는 인접 리스트를 활용하여 그래프를 관리하며, 최단 경로와 비용을 출력합니다.

    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>
    
    #define INF INT_MAX
    
    // Edge structure
    typedef struct {
        int src, dest, weight;
    } Edge;
    
    // Graph structure
    typedef struct {
        int V, E;
        Edge* edge;
    } Graph;
    
    // Function to create a graph with V vertices and E edges
    Graph* createGraph(int V, int E) {
        Graph* graph = (Graph*)malloc(sizeof(Graph));
        graph->V = V;
        graph->E = E;
        graph->edge = (Edge*)malloc(E * sizeof(Edge));
        return graph;
    }
    
    // Function to print the shortest path from source to destination
    void printPath(int parent[], int j) {
        if (parent[j] == -1) {
            printf("%d ", j);
            return;
        }
        printPath(parent, parent[j]);
        printf("%d ", j);
    }
    
    // The main function that runs Bellman-Ford algorithm
    void BellmanFord(Graph* graph, int src) {
        int V = graph->V;
        int E = graph->E;
        int* dist = (int*)malloc(V * sizeof(int));
        int* parent = (int*)malloc(V * sizeof(int));
    
        // Step 1: Initialize distances from src to all other vertices as INFINITE
        for (int i = 0; i < V; i++) {
            dist[i] = INF;
            parent[i] = -1;
        }
        dist[src] = 0;
    
        // Step 2: Relax all edges |V| - 1 times
        for (int i = 1; i <= V - 1; i++) {
            for (int j = 0; j < E; j++) {
                int u = graph->edge[j].src;
                int v = graph->edge[j].dest;
                int weight = graph->edge[j].weight;
                if (dist[u] != INF && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    parent[v] = u;
                }
            }
        }
    
        // Step 3: Check for negative-weight cycles
        for (int i = 0; i < E; i++) {
            int u = graph->edge[i].src;
            int v = graph->edge[i].dest;
            int weight = graph->edge[i].weight;
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                printf("Graph contains negative weight cycle\n");
                return;
            }
        }
    
        // Print the shortest path and cost from source to each vertex
        for (int i = 0; i < V; i++) {
            if (i != src) {
                if (dist[i] == INF) {
                    printf("There is no path from %d to %d\n", src, i);
                } else {
                    printf("Path from %d to %d: ", src, i);
                    printPath(parent, i);
                    printf("\nCost: %d\n\n", dist[i]);
                }
            }
        }
    
        free(dist);
        free(parent);
    }
    
    // Driver program to test above functions
    int main() {
        int V = 5; // Number of vertices in graph
        int E = 8; // Number of edges in graph
        Graph* graph = createGraph(V, E);
    
        // add edge 0-1 (or A-B in above figure)
        graph->edge[0].src = 0;
        graph->edge[0].dest = 1;
        graph->edge[0].weight = -1;
    
        // add edge 0-2 (or A-C in above figure)
        graph->edge[1].src = 0;
        graph->edge[1].dest = 2;
        graph->edge[1].weight = 4;
    
        // add edge 1-2 (or B-C in above figure)
        graph->edge[2].src = 1;
        graph->edge[2].dest = 2;
        graph->edge[2].weight = 3;
    
        // add edge 1-3 (or B-D in above figure)
        graph->edge[3].src = 1;
        graph->edge[3].dest = 3;
        graph->edge[3].weight = 2;
    
        // add edge 1-4 (or B-E in above figure)
        graph->edge[4].src = 1;
        graph->edge[4].dest = 4;
        graph->edge[4].weight = 2;
    
        // add edge 3-2 (or D-C in above figure)
        graph->edge[5].src = 3;
        graph->edge[5].dest = 2;
        graph->edge[5].weight = 5;
    
        // add edge 3-1 (or D-B in above figure)
        graph->edge[6].src = 3;
        graph->edge[6].dest = 1;
        graph->edge[6].weight = 1;
    
        // add edge 4-3 (or E-D in above figure)
        graph->edge[7].src = 4;
        graph->edge[7].dest = 3;
        graph->edge[7].weight = -3;
    
        BellmanFord(graph, 0);
    
        free(graph->edge);
        free(graph);
    
        return 0;
    }
    

    코드 설명

    1. 구조체 정의:

      • Edge: 그래프의 간선을 나타내는 구조체로, 출발점(src), 도착점(dest), 가중치(weight)를 포함합니다.
      • Graph: 전체 그래프를 나타내는 구조체로, 정점의 개수(V), 간선의 개수(E), 간선들의 배열(edge)을 포함합니다.
    2. 그래프 생성 함수:

      • createGraph: 정점과 간선의 개수를 받아서 그래프를 생성하고 메모리를 할당합니다.
    3. 최단 경로 출력 함수:

      • printPath: 재귀적으로 부모 노드들을 따라가면서 경로를 출력합니다.
    4. Bellman-Ford 알고리즘:

      • BellmanFord: 주어진 그래프와 시작점을 사용하여 최단 경로와 비용을 계산하고 출력합니다.
    5. 메인 함수:

      • 그래프를 초기화하고, 간선들을 추가한 후 Bellman-Ford 알고리즘을 실행하여 결과를 출력합니다.

    주의사항

    • 그래프에 음의 사이클이 존재할 경우, 벨만-포드 알고리즘은 이를 감지하여 알려줍니다.
    • 메모리 할당과 해제를 적절하게 관리해야 합니다.

    이 코드는 단일 시작점으로부터 모든 정점까지의 최단 경로를 찾고 출력하는 작업을 수행합니다. 코드를 실행하여 결과를 확인할 수 있습니다.