gpt-4o-2024-05-13· OpenAI WildChat-4.8M (AI2)
bellman-ford 알고리즘을 활용해서 adjacency list로 구현된 그래프를 순회해서 shortest path를 찾아서 path의 경로를 출력하고…
- User
bellman-ford 알고리즘을 활용해서 adjacency list로 구현된 그래프를 순회해서 shortest path를 찾아서 path의 경로를 출력하고 그 cost를 출력하는 함수를 C언어로
- 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; }코드 설명
-
구조체 정의:
Edge: 그래프의 간선을 나타내는 구조체로, 출발점(src), 도착점(dest), 가중치(weight)를 포함합니다.Graph: 전체 그래프를 나타내는 구조체로, 정점의 개수(V), 간선의 개수(E), 간선들의 배열(edge)을 포함합니다.
-
그래프 생성 함수:
createGraph: 정점과 간선의 개수를 받아서 그래프를 생성하고 메모리를 할당합니다.
-
최단 경로 출력 함수:
printPath: 재귀적으로 부모 노드들을 따라가면서 경로를 출력합니다.
-
Bellman-Ford 알고리즘:
BellmanFord: 주어진 그래프와 시작점을 사용하여 최단 경로와 비용을 계산하고 출력합니다.
-
메인 함수:
- 그래프를 초기화하고, 간선들을 추가한 후 Bellman-Ford 알고리즘을 실행하여 결과를 출력합니다.
주의사항
- 그래프에 음의 사이클이 존재할 경우, 벨만-포드 알고리즘은 이를 감지하여 알려줍니다.
- 메모리 할당과 해제를 적절하게 관리해야 합니다.
이 코드는 단일 시작점으로부터 모든 정점까지의 최단 경로를 찾고 출력하는 작업을 수행합니다. 코드를 실행하여 결과를 확인할 수 있습니다.
-