用迪杰斯特拉算法邻接表C语言求两站点最短路径
时间: 2023-07-10 14:17:52 浏览: 71
好的,我会尽力回答你的问题。
首先,我们需要了解什么是邻接表。邻接表是一种表示图的数据结构,它使用链表来存储每个节点的邻居节点。在邻接表中,每个节点都有一个链表,其中存储了所有与该节点相邻的节点。
接下来,我们可以使用迪杰斯特拉算法来求解两个站点之间的最短路径。迪杰斯特拉算法是一种用于解决带权重图的单源最短路径问题的算法。该算法可以计算出从源节点到图中所有其他节点的最短路径。
下面是使用邻接表和迪杰斯特拉算法求解两个站点最短路径的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_NODES 1000
#define INF 99999
// 邻接表节点结构体
typedef struct AdjListNode {
int dest;
int weight;
struct AdjListNode* next;
} AdjListNode;
// 邻接表结构体
typedef struct AdjList {
AdjListNode* head;
} AdjList;
// 图结构体
typedef struct Graph {
int V;
AdjList* array;
} Graph;
// 新建邻接表节点
AdjListNode* newAdjListNode(int dest, int weight) {
AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}
// 新建图
Graph* createGraph(int V) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->V = V;
graph->array = (AdjList*)malloc(V * sizeof(AdjList));
for (int i = 0; i < V; ++i) {
graph->array[i].head = NULL;
}
return graph;
}
// 添加边
void addEdge(Graph* graph, int src, int dest, int weight) {
AdjListNode* newNode = newAdjListNode(dest, weight);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListNode(src, weight);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// 打印解决方案
void printSolution(int dist[], int n) {
printf("Vertex\tDistance from Source\n");
for (int i = 0; i < n; ++i) {
printf("%d\t\t%d\n", i, dist[i]);
}
}
// 找到距离最小的节点
int minDistance(int dist[], bool sptSet[], int V) {
int min = INF, min_index;
for (int v = 0; v < V; ++v) {
if (sptSet[v] == false && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}
// 使用迪杰斯特拉算法求解最短路径
void dijkstra(Graph* graph, int src, int dest) {
int dist[MAX_NODES];
bool sptSet[MAX_NODES];
// 初始化距离和sptSet
for (int i = 0; i < graph->V; ++i) {
dist[i] = INF;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < graph->V - 1; ++count) {
int u = minDistance(dist, sptSet, graph->V);
sptSet[u] = true;
for (AdjListNode* v = graph->array[u].head; v != NULL; v = v->next) {
if (!sptSet[v->dest] && dist[u] != INF && dist[u] + v->weight < dist[v->dest]) {
dist[v->dest] = dist[u] + v->weight;
}
}
}
if (dist[dest] != INF) {
printf("The shortest path from %d to %d is: %d\n", src, dest, dist[dest]);
}
else {
printf("There is no path from %d to %d\n", src, dest);
}
}
int main() {
Graph* graph = createGraph(6);
addEdge(graph, 0, 1, 4);
addEdge(graph, 0, 2, 3);
addEdge(graph, 1, 2, 1);
addEdge(graph, 1, 3, 2);
addEdge(graph, 2, 3, 4);
addEdge(graph, 3, 4, 2);
addEdge(graph, 4, 5, 6);
dijkstra(graph, 0, 5);
return 0;
}
```
在这个例子中,我们创建了一个包含6个节点的图,并且使用addEdge函数添加了边。然后,我们调用了dijkstra函数来计算从源节点0到目标节点5之间的最短路径。
希望这个代码能够解决你的问题!