dijkstra构建最小生成树

Dijkstra算法是一种用于求解单源最短路径问题的经典算法，而不是用于构建最小生成树的算法。最小生成树是指在一个连通无向图中，找到一个包含所有顶点且边权重之和最小的树。

如果你想了解如何构建最小生成树，可以使用Prim算法或者Kruskal算法。下面是对这两种算法的简要介绍：

1. Prim算法：
- Prim算法是一种贪心算法，用于构建最小生成树。
- 算法从一个起始顶点开始，逐步扩展生成树，直到包含所有顶点为止。
- 在每一步中，选择与当前生成树相连的边中权重最小的边，并将其加入生成树。
- 重复上述步骤，直到生成树包含所有顶点。

相关问题

构建图的最小生成树或求最短路径C语言

最小生成树算法：

使用Prim算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

void prim(int start_vertex) {
    bool visited[MAX_VERTICES] = {false}; // 顶点是否已被访问
    int distance[MAX_VERTICES]; // 到各顶点的距离
    int parent[MAX_VERTICES]; // 生成树的父节点

    // 初始化
    for (int i = 0; i < num_vertices; i++) {
        visited[i] = false;
        distance[i] = INF;
        parent[i] = -1;
    }
    distance[start_vertex] = 0;

    for (int i = 0; i < num_vertices - 1; i++) { // 循环n-1次，构建n-1条边
        int min_distance = INF;
        int u; // 最小距离对应的顶点编号
        // 找到未被访问过的、到起点距离最短的顶点
        for (int j = 0; j < num_vertices; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                u = j;
            }
        }
        visited[u] = true; // 对该顶点进行标记
        // 更新与该顶点相邻的顶点到起点的距离
        for (int v = 0; v < num_vertices; v++) {
            if (adj_matrix[u][v] != 0 && !visited[v] && adj_matrix[u][v] < distance[v]) {
                distance[v] = adj_matrix[u][v];
                parent[v] = u;
            }
        }
    }

    // 输出生成树
    printf("生成树：\n");
    for (int i = 1; i < num_vertices; i++) { // 从第二个顶点开始，依次输出每个顶点的父节点和边的权值
        printf("%d - %d (%d)\n", parent[i], i, adj_matrix[i][parent[i]]);
    }
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    printf("请输入起点编号：");
    int start_vertex;
    scanf("%d", &start_vertex);
    prim(start_vertex);
    return 0;
}

使用Kruskal算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

int parent[MAX_VERTICES]; // 并查集数组

// 并查集查找根节点
int find(int x) {
    while (parent[x] != -1) {
        x = parent[x];
    }
    return x;
}

void kruskal() {
    int total_weight = 0; // 最小生成树的总权值
    int edge_count = 0; // 已选取的边的数量

    // 初始化并查集
    for (int i = 0; i < num_vertices; i++) {
        parent[i] = -1;
    }

    // 对所有边按权值从小到大排序
    struct {
        int u, v, weight;
    } edges[num_vertices * num_vertices]; // 边的数组，最多有n^2条边
    int count = 0; // 实际边的数量
    for (int i = 0; i < num_vertices; i++) {
        for (int j = i + 1; j < num_vertices; j++) { // 使用邻接矩阵，只需要遍历矩阵的上三角
            if (adj_matrix[i][j] != 0) {
                edges[count].u = i;
                edges[count].v = j;
                edges[count].weight = adj_matrix[i][j];
                count++;
            }
        }
    }
    for (int i = 0; i < count - 1; i++) { // 冒泡排序
        for (int j = 0; j < count - i - 1; j++) {
            if (edges[j].weight > edges[j+1].weight) {
                struct {
                    int u, v, weight;
                } temp = edges[j];
                edges[j] = edges[j+1];
                edges[j+1] = temp;
            }
        }
    }

    // 依次选取权值最小的边，如果两个顶点不在同一个连通分量中，则加入最小生成树
    printf("生成树：\n");
    while (edge_count < num_vertices - 1) { // 已选取的边的数量小于n-1时，继续选取
        int u = edges[edge_count].u;
        int v = edges[edge_count].v;
        int weight = edges[edge_count].weight;
        int root_u = find(u);
        int root_v = find(v);
        if (root_u != root_v) { // 如果两个顶点不在同一个连通分量中
            parent[root_u] = root_v; // 合并连通分量
            printf("%d - %d (%d)\n", u, v, weight); // 输出边
            total_weight += weight; // 加上边的权值
        }
        edge_count++;
    }
    printf("最小权值和：%d\n", total_weight);
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    kruskal();
    return 0;
}

最短路径算法：

使用Dijkstra算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

void dijkstra(int start_vertex) {
    bool visited[MAX_VERTICES] = {false}; // 顶点是否已被访问
    int distance[MAX_VERTICES]; // 起点到各顶点的距离

    // 初始化
    for (int i = 0; i < num_vertices; i++) {
        visited[i] = false;
        distance[i] = INF;
    }
    distance[start_vertex] = 0;

    for (int i = 0; i < num_vertices; i++) { // 循环n次，每次确定一个顶点的最短路径
        int min_distance = INF;
        int u; // 最小距离对应的顶点编号
        // 找到未被访问过的、到起点距离最短的顶点
        for (int j = 0; j < num_vertices; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                u = j;
            }
        }
        visited[u] = true; // 对该顶点进行标记
        // 更新与该顶点相邻的顶点到起点的距离
        for (int v = 0; v < num_vertices; v++) {
            if (adj_matrix[u][v] != 0 && !visited[v] && distance[u] + adj_matrix[u][v] < distance[v]) {
                distance[v] = distance[u] + adj_matrix[u][v];
            }
        }
    }

    // 输出到各顶点的最短路径
    printf("起点到各顶点的最短路径：\n");
    for (int i = 0; i < num_vertices; i++) {
        printf("%d -> %d: %d\n", start_vertex, i, distance[i]);
    }
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    printf("请输入起点编号：");
    int start_vertex;
    scanf("%d", &start_vertex);
    dijkstra(start_vertex);
    return 0;
}

使用Bellman-Ford算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

void bellman_ford(int start_vertex) {
    int distance[MAX_VERTICES]; // 起点到各顶点的距离

    // 初始化
    for (int i = 0; i < num_vertices; i++) {
        distance[i] = INF;
    }
    distance[start_vertex] = 0;

    for (int i = 0; i < num_vertices - 1; i++) { // 循环n-1次，每次松弛n-1条边
        for (int u = 0; u < num_vertices; u++) {
            for (int v = 0; v < num_vertices; v++) {
                if (adj_matrix[u][v] != 0 && distance[u] + adj_matrix[u][v] < distance[v]) {
                    distance[v] = distance[u] + adj_matrix[u][v];
                }
            }
        }
    }

    // 判断是否存在负权回路
    bool has_negative_cycle = false;
    for (int u = 0; u < num_vertices; u++) {
        for (int v = 0; v < num_vertices; v++) {
            if (adj_matrix[u][v] != 0 && distance[u] + adj_matrix[u][v] < distance[v]) {
                has_negative_cycle = true;
                break;
            }
        }
    }

    if (has_negative_cycle) {
        printf("图中存在负权回路\n");
    } else {
        // 输出到各顶点的最短路径
        printf("起点到各顶点的最短路径：\n");
        for (int i = 0; i < num_vertices; i++) {
            printf("%d -> %d: %d\n", start_vertex, i, distance[i]);
        }
    }
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    printf("请输入起点编号：");
    int start_vertex;
    scanf("%d", &start_vertex);
    bellman_ford(start_vertex);
    return 0;
}

构建图的最小生成树或求最短路径。(二选一部分) (1)、用Prim法求连通图的最小生成树（邻接表） (2)、用Dijkstra算法求某一确定顶点到所有其它顶点的最短路径，请在网上寻找到这段话

好的，以下是用Prim算法求连通图的最小生成树的Python实现（使用邻接表表示图）：

import heapq

def prim(graph):
    # 任选一个顶点作为起点
    start = list(graph.keys())[0]

    # 初始化距离字典、已知最短路径集合和边集合
    distance = {vertex: float('inf') for vertex in graph}
    distance[start] = 0
    visited = set()
    edges = []

    # 堆优化的Prim算法
    heap = [(0, start)]
    while heap:
        (dist, current_vertex) = heapq.heappop(heap)

        # 如果当前顶点已经在已知最短路径集合中，跳过
        if current_vertex in visited:
            continue

        visited.add(current_vertex)

        # 将当前顶点与已知最短路径集合中的顶点之间的边加入边集合中
        if current_vertex != start:
            edges.append((distance[current_vertex], current_vertex, parent))

        # 更新与当前顶点相邻的顶点的距离
        for neighbor, weight in graph[current_vertex].items():
            if neighbor not in visited:
                if weight < distance[neighbor]:
                    distance[neighbor] = weight
                    heapq.heappush(heap, (weight, neighbor))
                    parent = current_vertex

    # 返回边集合
    return edges

其中，graph是邻接表表示的图。这个实现中使用了堆优化，可以有效地加速算法。

以下是用Dijkstra算法求某一确定顶点到所有其它顶点的最短路径的Python实现（使用邻接表表示图）：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典和已知最短路径集合
    distance = {vertex: float('inf') for vertex in graph}
    distance[start] = 0
    visited = set()

    # 堆优化的Dijkstra算法
    heap = [(0, start)]
    while heap:
        (dist, current_vertex) = heapq.heappop(heap)

        # 如果当前顶点已经在已知最短路径集合中，跳过
        if current_vertex in visited:
            continue

        visited.add(current_vertex)

        # 更新与当前顶点相邻的顶点的距离
        for neighbor, weight in graph[current_vertex].items():
            if neighbor not in visited:
                new_distance = dist + weight
                if new_distance < distance[neighbor]:
                    distance[neighbor] = new_distance
                    heapq.heappush(heap, (new_distance, neighbor))

    # 返回距离字典
    return distance

其中，graph是邻接表表示的图，start是起点。这个实现中使用了堆优化，可以有效地加速算法。