[已解决]迪杰斯特拉算法用邻接表存储赋权图

好故事慢慢来

迪杰斯特拉算法用邻接表存储赋权图怎么实现；用c语言，谢谢嘞

最佳答案

月排行榜 / 总排行榜

isdkz

2023-6-13 20:56:40

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[i] = NULL;
        graph->distance[i] = INFINITY;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest, int weight) {
    // 从src到dest的边
    node* newNode = createNode(dest, weight);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 在无向图中添加从dest到src的边
    newNode = createNode(src, weight);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

然后，我们需要实现Dijkstra算法本身：

// 找到距离源顶点最近的顶点
int findMinVertex(Graph* graph, int* visited) {
    int minVertex = -1;
    for (int i = 0; i < graph->numVertices; i++) {
        if (!visited[i] && (minVertex == -1 || graph->distance[i] < graph->distance[minVertex])) {
            minVertex = i;
        }
    }
    return minVertex;
}

// 执行Dijkstra算法
void dijkstra(Graph* graph, int startVertex) {
    int visited[MAX] = {0};
    graph->distance[startVertex] = 0;

    for (int i = 0; i < graph->numVertices - 1; i++) {
        int minVertex = findMinVertex(graph, visited);
        visited[minVertex] = 1;

        node* adjList = graph->adjLists[minVertex];
        while (adjList != NULL) {
            int adjVertex = adjList->vertex;
            if (!visited[adjVertex] && graph->distance[minVertex] != INFINITY
                && graph->distance[adjVertex] > graph->distance[minVertex] + adjList->weight) {
                graph->distance[adjVertex] = graph->distance[minVertex] + 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[i]);
}

最后，我们可以在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算法的例子。

跳转到最佳答案楼层

isdkz

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[i] = NULL;
        graph->distance[i] = INFINITY;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest, int weight) {
    // 从src到dest的边
    node* newNode = createNode(dest, weight);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 在无向图中添加从dest到src的边
    newNode = createNode(src, weight);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

然后，我们需要实现Dijkstra算法本身：

// 找到距离源顶点最近的顶点
int findMinVertex(Graph* graph, int* visited) {
    int minVertex = -1;
    for (int i = 0; i < graph->numVertices; i++) {
        if (!visited[i] && (minVertex == -1 || graph->distance[i] < graph->distance[minVertex])) {
            minVertex = i;
        }
    }
    return minVertex;
}

// 执行Dijkstra算法
void dijkstra(Graph* graph, int startVertex) {
    int visited[MAX] = {0};
    graph->distance[startVertex] = 0;

    for (int i = 0; i < graph->numVertices - 1; i++) {
        int minVertex = findMinVertex(graph, visited);
        visited[minVertex] = 1;

        node* adjList = graph->adjLists[minVertex];
        while (adjList != NULL) {
            int adjVertex = adjList->vertex;
            if (!visited[adjVertex] && graph->distance[minVertex] != INFINITY
                && graph->distance[adjVertex] > graph->distance[minVertex] + adjList->weight) {
                graph->distance[adjVertex] = graph->distance[minVertex] + 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[i]);
}

最后，我们可以在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算法的例子。