迪杰斯特拉算法用邻接表存储赋权图
迪杰斯特拉算法用邻接表存储赋权图怎么实现；用c语言，谢谢嘞Dijkstra算法是一种常用的最短路径算法，下面我会用C语言展示一个利用邻接表来存储赋权图的版本。首先，我们需要定义邻接表的节点结构和邻接表本身的结构：
#include <stdio.h>
#include <stdlib.h>
#define INFINITY 999999
#define MAX 10
// 邻接表的节点结构
typedef struct node {
int vertex; // 顶点编号
int weight; // 边的权值
struct node* next;// 指向下一个节点的指针
} node;
// 邻接表的结构
typedef struct Graph {
int numVertices; // 顶点数量
struct node** adjLists; // 邻接表数组
int* distance; // 保存每个顶点到源顶点的最短距离
} Graph;
// 创建节点
node* createNode(int v, int weight) {
node* newNode = malloc(sizeof(node));
newNode->vertex = v;
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}
// 创建图
Graph* createGraph(int vertices) {
Graph* graph = malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(node*));
graph->distance = malloc(vertices * sizeof(int));
int i;
for (i = 0; i < vertices; i++) {
graph->adjLists = NULL;
graph->distance = INFINITY;
}
return graph;
}
// 添加边
void addEdge(Graph* graph, int src, int dest, int weight) {
// 从src到dest的边
node* newNode = createNode(dest, weight);
newNode->next = graph->adjLists;
graph->adjLists = newNode;
// 在无向图中添加从dest到src的边
newNode = createNode(src, weight);
newNode->next = graph->adjLists;
graph->adjLists = newNode;
}
然后，我们需要实现Dijkstra算法本身：
// 找到距离源顶点最近的顶点
int findMinVertex(Graph* graph, int* visited) {
int minVertex = -1;
for (int i = 0; i < graph->numVertices; i++) {
if (!visited && (minVertex == -1 || graph->distance < graph->distance)) {
minVertex = i;
}
}
return minVertex;
}
// 执行Dijkstra算法
void dijkstra(Graph* graph, int startVertex) {
int visited = {0};
graph->distance = 0;
for (int i = 0; i < graph->numVertices - 1; i++) {
int minVertex = findMinVertex(graph, visited);
visited = 1;
node* adjList = graph->adjLists;
while (adjList != NULL) {
int adjVertex = adjList->vertex;
if (!visited && graph->distance != INFINITY
&& graph->distance > graph->distance + adjList->weight) {
graph->distance = graph->distance + adjList->weight;
}
adjList = adjList->next;
}
}
}
// 打印结果
void printGraph(Graph* graph) {
for (int i = 0; i < graph->numVertices; i++)
printf("Vertex %d -> distance = %d\n", i, graph->distance);
}
最后，我们可以在main函数中测试这个算法：
int main() {
Graph* graph = createGraph(6);
addEdge(graph, 0, 1, 4);
addEdge(graph, 0, 2, 2);
addEdge(graph, 1, 2, 1);
addEdge(graph, 1, 3, 5);
addEdge(graph, 2, 3, 8);
addEdge(graph, 2, 4, 10);
addEdge(graph, 3, 5, 6);
addEdge(graph, 4, 5, 2);
dijkstra(graph, 0);
printGraph(graph);
return 0;
}
以上就是一个基于邻接表实现的Dijkstra算法的例子。
页:
[1]