邻接表实现dijkstra算法

邻接表是一种常用的图的表示方法，它通过链表的形式存储图的顶点和边的信息。Dijkstra算法是一种用于求解单源最短路径的算法，它可以在带权重的有向图中找到从起始顶点到其他所有顶点的最短路径。

邻接表实现Dijkstra算法的步骤如下：
1. 创建一个空的距离数组dist[]，用于存储起始顶点到其他顶点的最短距离。将起始顶点的距离初始化为0，其他顶点的距离初始化为无穷大。
2. 创建一个优先队列（最小堆）minHeap，用于存储待处理的顶点及其对应的最短距离。
3. 将起始顶点及其距离加入到minHeap中。
4. 循环执行以下步骤，直到minHeap为空：
- 从minHeap中取出距离最小的顶点u。
- 遍历顶点u的所有邻接顶点v：
- 如果从起始顶点到v的距离（dist[v]）大于从起始顶点到u再到v的距离（dist[u] + weight(u, v)），则更新dist[v]为dist[u] + weight(u, v)。
- 将顶点v及其更新后的距离加入到minHeap中。
5. 循环结束后，dist[]数组中存储的就是起始顶点到其他所有顶点的最短距离。

相关问题

用邻接表实现Dijkstra算法

邻接表是一种常用的图的表示方法，它将每个顶点与其相邻的顶点列表关联起来。Dijkstra算法是一种用于解决单源最短路径问题的贪心算法。下面是用邻接表实现Dijkstra算法的示例代码：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，将起始节点的距离设为0，其他节点的距离设为无穷大
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # 使用优先队列来存储节点和对应的距离
    queue = [(0, start)]

    while queue:
        # 取出距离最小的节点
        current_distance, current_node = heapq.heappop(queue)

        # 如果当前节点的距离已经大于已知的最短距离，则跳过
        if current_distance > distances[current_node]:
            continue

        # 遍历当前节点的邻居节点
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # 如果通过当前节点到达邻居节点的距离更短，则更新最短距离
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

# 示例图的邻接表表示
graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}

start_node = 'A'
distances = dijkstra(graph, start_node)

print("最短路径：")
for node, distance in distances.items():
    print(f"从节点 {start_node} 到节点 {node} 的最短距离为 {distance}")

这段代码使用了优先队列来优化取最小权值边的时间复杂度，通过遍历邻居节点并更新最短距离来找到从起始节点到其他节点的最短路径。最后，打印出从起始节点到每个节点的最短距离。

c语言代码邻接表实现dijkstra算法求单源最短路径

以下是使用邻接表实现Dijkstra算法求单源最短路径的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 1000

typedef struct Edge {
    int dest;
    int weight;
    struct Edge* next;
} Edge;

typedef struct Node {
    Edge* head;
} Node;

typedef struct Graph {
    int num_vertices;
    Node nodes[MAX_VERTICES];
} Graph;

Graph* create_graph(int num_vertices) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->num_vertices = num_vertices;
    for (int i = 0; i < num_vertices; i++)
        graph->nodes[i].head = NULL;
    return graph;
}

Edge* create_edge(int dest, int weight) {
    Edge* edge = (Edge*) malloc(sizeof(Edge));
    edge->dest = dest;
    edge->weight = weight;
    edge->next = NULL;
    return edge;
}

void add_edge(Graph* graph, int src, int dest, int weight) {
    Edge* edge = create_edge(dest, weight);
    edge->next = graph->nodes[src].head;
    graph->nodes[src].head = edge;
}

int min_distance(int dist[], int visited[], int num_vertices) {
    int min_dist = INT_MAX, min_vertex;
    for (int i = 0; i < num_vertices; i++) {
        if (!visited[i] && dist[i] < min_dist) {
            min_dist = dist[i];
            min_vertex = i;
        }
    }
    return min_vertex;
}

void print_solution(int dist[], int num_vertices) {
    printf("Vertex\tDistance from Source\n");
    for (int i = 0; i < num_vertices; i++)
        printf("%d\t%d\n", i, dist[i]);
}

void dijkstra(Graph* graph, int src) {
    int dist[MAX_VERTICES];
    int visited[MAX_VERTICES];
    for (int i = 0; i < graph->num_vertices; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }
    dist[src] = 0;
    for (int i = 0; i < graph->num_vertices - 1; i++) {
        int u = min_distance(dist, visited, graph->num_vertices);
        visited[u] = 1;
        for (Edge* edge = graph->nodes[u].head; edge != NULL; edge = edge->next) {
            int v = edge->dest;
            int weight = edge->weight;
            if (!visited[v] && dist[u] != INT_MAX && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }
    print_solution(dist, graph->num_vertices);
}

int main() {
    int num_vertices = 5;
    Graph* graph = create_graph(num_vertices);
    add_edge(graph, 0, 1, 10);
    add_edge(graph, 0, 4, 5);
    add_edge(graph, 1, 2, 1);
    add_edge(graph, 1, 4, 2);
    add_edge(graph, 2, 3, 4);
    add_edge(graph, 3, 2, 6);
    add_edge(graph, 3, 0, 7);
    add_edge(graph, 4, 1, 3);
    add_edge(graph, 4, 2, 9);
    dijkstra(graph, 0);
    return 0;
}

这里实现的Dijkstra算法使用了邻接表来表示图，使用了堆排序的思想来寻找当前距离源点最近的未访问过的节点，以提高算法效率。