用c实现diikstra算法

news/2024/7/15 18:55:00 标签: 算法, c语言, 图论

下面是用C语言实现Dijkstra算法的示例代码。Dijkstra算法用于在带权重的图中找到从源点到所有其他顶点的最短路径。这里,我们假设使用邻接矩阵来表示图,并且图中没有负权重的边。

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

#define V 9 // 图中顶点的数量

// 寻找最短路径树集合中距离最短的顶点
int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == 0 && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

// 打印构造的距离数组
void printSolution(int dist[]) {
    printf("Vertex \t\t Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}

// 使用Dijkstra算法实现函数
void dijkstra(int graph[V][V], int src) {
    int dist[V]; // 输出数组。dist[i]将保存从源到顶点i的最短距离
    int sptSet[V]; // sptSet[i]为真,如果顶点i在最短路径树中,或者最短距离从src到i已经确定

    // 初始化所有距离为无穷大,sptSet[]为假
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = 0;

    // 源顶点到自身的距离始终为0
    dist[src] = 0;

    // 找到所有顶点的最短路径
    for (int count = 0; count < V - 1; count++) {
        // 选择最短距离顶点的最小距离顶点。u始终等于src在第一次迭代中
        int u = minDistance(dist, sptSet);

        // 标记选定的顶点为已处理
        sptSet[u] = 1;

        // 更新相邻顶点的距离值
        for (int v = 0; v < V; v++)

            // 更新dist[v]仅当没有在sptSet中,有从u到v的边,
            // 并且总权重路径从src到v通过u小于当前dist[v]的值
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                                       && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    // 打印构造的距离数组
    printSolution(dist);
}

int main() {
    // 以邻接矩阵形式表示的图
    int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                       {4, 0, 8, 0, 0, 0, 0, 11, 0},
                       {0, 8, 0, 7, 0, 4, 0, 0, 2},
                       {0, 0, 7, 0, 9, 14, 0, 0, 0},
                       {0, 0, 0, 9, 0, 10, 0, 0, 0},
                       {0, 0, 4, 14, 10, 0, 2, 0, 0},
                       {0, 0, 0, 0, 0, 2, 0, 1, 6},
                       {8, 11, 0, 0, 0, 0, 1, 0, 7},
                       {0, 0, 2, 0, 0, 0, 6, 7, 0}};

    dijkstra(graph, 0); //

 0 作为源顶点

    return 0;
}

在这个程序中,我们首先定义了一个名为minDistance的函数,它从那些尚未被包含在最短路径树中的顶点集中挑出距离源点最近的顶点。接下来,我们定义了dijkstra函数,它实现了Dijkstra算法,并使用minDistance函数来选择下一个要处理的顶点。dijkstra函数首先初始化所有顶点的距离为无限大,然后逐步找出到每个顶点的最短路径。最后,我们在main函数中定义了图并调用了dijkstra函数。


http://www.niftyadmin.cn/n/5386370.html

相关文章

webpack配置杂记

1、热更新 安装webpack-dev-server : npm i webpack-dev-server -D webpack.config.js配置 module.exports {// 其他配置...,// 热更新配置devServer: {host: "localhost",port: 3000,}, } 2、入口entry&#xff1a;使用相对路径们也就是webpack程序运行的路径&am…

汇川伺服驱动器参数整理

基本参数&#xff1a; 基本控制参数&#xff1a; 控制模式选择&#xff1a;转矩控制、速度控制、位置控制 绝对位置检测系统选择&#xff1a;增量位置模式、绝对位置线性模式、绝对位置旋转模式 旋转正方向选择&#xff1a;以CCW方向为正转方向、以…

[ Python+OpenCV+Mediapipe ] 实现对象识别

一、写在前面 本文所用例子为个人学习的小结&#xff0c;如有不足之处请各位多多海涵&#xff0c;欢迎小伙伴一起学习进步&#xff0c;如果想法可在评论区指出&#xff0c;我会尽快回复您&#xff0c;不胜感激&#xff01; 所公布代码或截图均为运行成功后展示。 二、本文内容…

java 中开源的html解析库Jsoup 简单例子

下面是一个使用Jsoup库解析HTML的简单Java例子。这个例子展示了如何使用Jsoup从一个HTML字符串中提取数据。 首先&#xff0c;确保你已经将Jsoup作为依赖项添加到你的项目中。如果你使用的是Maven&#xff0c;可以在pom.xml文件中添加以下依赖&#xff1a; &…

数字新纪元:探索Web3对社会的影响

在当今数字化时代&#xff0c;技术的进步已经成为社会发展的驱动力之一。而随着区块链技术的快速发展&#xff0c;我们正处在一个即将到来的数字新纪元——Web3时代。这一新时代不仅仅是技术的迭代升级&#xff0c;更是对传统社会模式的颠覆和重构。本文将深入探讨Web3对社会的…

基于深度学习的红肉新鲜过期判决系统matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 4.1 系统构成与流程 4.2 模型训练与优化 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 MATLAB2022a 3.部分核心程序 ...............................................…

2023年06月CCF-GESP编程能力等级认证C++编程四级真题解析

一、单选题(每题 2 分,共 30 分) 第1题 高级语言编写的程序需要经过以下( )操作,可以生成在计算机上运行的可执行代码。 A. 编辑 B. 保存 C. 调试 D. 编译 答案:D 第2题 排序算法是稳定的(Stable Sorting),就是指排序算法可以保证,在待排序数据中有两个相等记录…

day4 2/21

1>使用多线程完成两个文件的拷贝&#xff0c;第一个线程拷贝前一半&#xff0c;第二个线程拷贝后一半&#xff0c;主线程回收两个线程的资源 #include<myhead.h> typedef struct Inof {const char*srcfile;const char*destfile;int start;int len; }inof;int do_len…