c语言单源最短距离包含三种算法的代码Dijkstra算法、SPFA算法、Bellman-Ford算法

好的，下面是使用C语言实现Dijkstra算法、SPFA算法和Bellman-Ford算法的代码示例： 1. Dijkstra算法： ```c #include <stdio.h> #include <stdbool.h> #define INF 99999 #define V 6 int minDistance(int dist[], bool visited[]) { int min = INF, min_index; for (int v = 0; v < V; v++) { if (visited[v] == false && dist[v] <= min) { min = dist[v]; min_index = v; } } return min_index; } void printSolution(int dist[]) { printf("Vertex\tDistance from Source\n"); for (int i = 0; i < V; i++) { printf("%d\t%d\n", i, dist[i]); } } void dijkstra(int graph[V][V], int source) { int dist[V]; bool visited[V]; for (int i = 0; i < V; i++) { dist[i] = INF; visited[i] = false; } dist[source] = 0; for (int count = 0; count < V - 1; count++) { int u = minDistance(dist, visited); visited[u] = true; for (int v = 0; v < V; v++) { if (!visited[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) { dist[v] = dist[u] + graph[u][v]; } } } printSolution(dist); } int main() { int graph[V][V] = { {0, 4, 0, 0, 0, 0}, {4, 0, 8, 0, 0, 0}, {0, 8, 0, 7, 0, 4}, {0, 0, 7, 0, 9, 14}, {0, 0, 0, 9, 0, 10}, {0, 0, 4, 14, 10, 0} }; dijkstra(graph, 0); return 0; } ``` 2. SPFA算法： ```c #include <stdio.h> #include <stdbool.h> #include <limits.h> #define V 5 // 图中顶点的数量 typedef struct { int u; int v; int weight; } Edge; void printSolution(int dist[]) { printf("Vertex\tDistance from Source\n"); for (int i = 0; i < V; i++) { printf("%d\t%d\n", i, dist[i]); } } void spfa(int graph[V][V], int source) { int dist[V]; bool inQueue[V]; for (int i = 0; i < V; i++) { dist[i] = INT_MAX; inQueue[i] = false; } dist[source] = 0; // 创建一个队列，用于存储顶点索引 int queue[V]; int front = -1; int rear = -1; // 将起始顶点加入队列 queue[++rear] = source; inQueue[source] = true; while (front != rear) { int u = queue[++front]; inQueue[u] = false; for (int v = 0; v < V; v++) { if (graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) { dist[v] = dist[u] + graph[u][v]; if (!inQueue[v]) { queue[++rear] = v; inQueue[v] = true; } } } } printSolution(dist); } int main() { int graph[V][V] = { {0, 4, 0, 0, 0}, {4, 0, 8, 0, 0}, {0, 8, 0, 7, 0}, {0, 0, 7, 0, 9}, {0, 0, 0, 9, 0} }; spfa(graph, 0); return 0; } ``` 3. Bellman-Ford算法： ```c #include <stdio.h> #include <stdbool.h> #include <limits.h> #define V 5 // 图中顶点的数量 #define E 8 // 图中边的数量 typedef struct { int u; int v; int weight; } Edge; void printSolution(int dist[]) { printf("Vertex\tDistance from Source\n"); for (int i = 0; i < V; i++) { printf("%d\t%d\n", i, dist[i]); } } void bellmanFord(Edge edges[], int source) { int dist[V]; for (int i = 0; i < V; i++) { dist[i] = INT_MAX; } dist[source] = 0; for (int i = 1; i < V; i++) { for (int j = 0; j < E; j++) { int u = edges[j].u; int v = edges[j].v; int weight = edges[j].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; } } } // 检查是否存在负权回路 for (int i = 0; i < E; i++) { int u = edges[i].u; int v = edges[i].v; int weight = edges[i].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) { printf("Graph contains negative weight cycle\n"); return; } } printSolution(dist); } int main() { Edge edges[E] = { {0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2}, {1, 4, 2}, {3, 2, 5}, {3, 1, 1}, {4, 3, -3} }; bellmanFord(edges, 0); return 0; } ``` 以上是使用C语言实现Dijkstra算法、SPFA算法和Bellman-Ford算法的代码示例。希望对你有所帮助！