热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

最短路径算法的编程与实现C语言

1.掌握最短路径算法的基本原理及编程实现;operatingsystemversion:Win11CPUinstructionset:x64IntegratedDevelopmen
一 、目的:

1.掌握最短路径算法的基本原理及编程实现;

二 、环境:

operating system version:Win11
CPU instruction set:  x64
Integrated Development Environment:Viusal Studio 2022

三 、内容:

1)建立一张图,选择一种存储结构(邻接矩阵或邻接表)初始化该图;
2)用Dijkstra算法实现点与点之间的最短路径。

四 、要求:

1) 实现图的两种表示方法;
2) 实现Dijkstra算法;

五 、步骤:

1. 程序:
 

#include #define MVNum 100 #define MaxInt 32767 //极大值,即∞ using namespace std; typedef int ArcType; typedef char VerTextType[20]; int* D = new int[MVNum]; bool* S = new bool[MVNum]; int* Path = new int[MVNum]; typedef struct ArcNode //边结点 { int adjver; //该边所指向的顶点位置 struct ArcNode* nextarc; //指向下一条边的指针 ArcType weight; } ArcNode; typedef struct VNode //顶点信息 { VerTextType data; ArcNode* firstarc; } VNode, AdjList[MVNum]; typedef struct node { AdjList vertices; int vexnum; //图的当前顶点数 int arcnum; //图的当前边数 } ALGraph; //临接表存储方式最短路径(dijkstra),复杂度O(n^2) void ShortestPath_DIJ2(ALGraph G, int v0, ArcType D[], int Path[]) { int ok[MVNum], i, j; // ok数组标记是否确定最短路径 for (i = 0; i adjver] == 0 && D[cur->adjver] > D[min_node] + cur->weight) { D[cur->adjver] = D[min_node] + cur->weight; Path[cur->adjver] = min_node; } cur = cur->nextarc; } } } //图的邻接矩阵 typedef struct { char vexs[MVNum]; //顶点表 int arcs[MVNum][MVNum]; //邻接矩阵 }Graph; void InitGraph(Graph& G, int vex) { cout <<"输入点的名称,如a" <> G.vexs[i]; } cout <> v1 >> v2 >> o; i = LocateVex(G, v1, vex); j = LocateVex(G, v2, vex); G.arcs[j][i] = G.arcs[i][j] = o; } } void DisplayGraph(Graph G, int vex) { int i, j; for (i = 0; i > vexnum >> arcnum; cout <

2.程序结果:

1)程序运行,我使用的测试数据如下所示:

2)我采用邻接矩阵的方式实现最短路径的存储。创建的无向图G如下:

3)最终通过Dijkstra算法输出源点0到其余节点的最短路径如下:

六 、小结:

       此次是关于Dijkstra最短路径算法的编程与实现。我先分别尝试了采用邻接矩阵以及邻接表的存储结构,比较了他们的优缺点:其中图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。从这个矩阵中,可以较容易知道图中的信息。1)可以判断任意两顶点是否有边无边;2)可以知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点;而邻接表则是将图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储。图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表。

        最终我在构建图的时候选择了邻接矩阵的方式实现。通过邻接矩阵的Dijkstra时间复杂度是O(N2)。其中每次找到离1号顶点最近的顶点的时间复杂度是 O(N)。整个程序的基本思想是:设置两个顶点集S和T,集合S中存放已经找到最短路径的顶点,集合T中存放着当前还未找到最短路径的顶点;初始状态下,集合S中只包含源点V1,T中为除了源点以外的其他顶点,此时源点到各顶点的最短路径为两个顶点所连的边上的权值,若是源点V1到该顶点没有边,则最小路径为无穷大;从集合T中选取到源点V1的路径长度最短的顶点Vi加入到集合S中;修改源点V1到集合T中剩余顶点Vj的最短路径长度。新的最短路径长度值为Vj原来的最短路径长度值与顶点Vi的最短路径长度加上Vi到Vj的路径长度值中的较小者;不断重复步骤三、4,直至集合T的顶点所有加入到集合S中。


推荐阅读
  • 个人博客:打开链接依赖倒置原则定义依赖倒置原则(DependenceInversionPrinciple,DIP)定义如下:Highlevelmo ... [详细]
  • 如何使用Maven将依赖插件一并打包进JAR文件
    本文详细介绍了在使用Maven构建项目时,如何将所需的依赖插件一同打包进最终的JAR文件中,以避免手动部署依赖库的麻烦。 ... [详细]
  • 本文介绍了一种在 Android 开发中动态修改 strings.xml 文件中字符串值的有效方法。通过使用占位符,开发者可以在运行时根据需要填充具体的值,从而提高应用的灵活性和可维护性。 ... [详细]
  • 解决Expo XDE 2.22.1版本启动错误
    根据问题描述,用户在将Expo升级至2.22.1版本后,在尝试打开项目时遇到了错误。本文提供了详细的错误分析及解决方案。 ... [详细]
  • 本文详细介绍了如何使用Linux下的mysqlshow命令来查询MySQL数据库的相关信息,包括数据库、表以及字段的详情。通过本文的学习,读者可以掌握mysqlshow命令的基本语法及其常用选项。 ... [详细]
  • 使用Java计算两个日期之间的月份数
    本文详细介绍了利用Java编程语言计算两个指定日期之间月份数的方法。文章通过实例代码讲解了如何使用Joda-Time库来简化日期处理过程,旨在为开发者提供一个高效且易于理解的解决方案。 ... [详细]
  • 汇编语言标识符和表达式(四)(表达式与符号定义语句)
    7、表达式表达式是程序设计课程里的一个重要的基本概念,它可由运算符、操作符、括号、常量和一些符号连在一起的式子。在汇编语言中,表达式分为:数值表达式和地址表达式。(1)进制伪指令R ... [详细]
  • C/C++ 应用程序的安装与卸载解决方案
    本文介绍了如何使用Inno Setup来创建C/C++应用程序的安装程序,包括自动检测并安装所需的运行库,确保应用能够顺利安装和卸载。 ... [详细]
  • 本文详细介绍了 Node.js 中 OS 模块的 arch 方法,包括其功能、语法、参数以及返回值,并提供了具体的使用示例。 ... [详细]
  • 本文详细介绍了如何在 Ubuntu 14.04 系统上搭建仅使用 CPU 的 Caffe 深度学习框架,包括环境准备、依赖安装及编译过程。 ... [详细]
  • 本文探讨了Python类型注解使用率低下的原因,主要归结于历史背景和投资回报率(ROI)的考量。文章不仅分析了类型注解的实际效用,还回顾了Python类型注解的发展历程。 ... [详细]
  • Android 中的布局方式之线性布局
    nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]
  • 深入解析C语言中的关键字及其分类
    本文将全面介绍C语言中的关键字,并按照功能将其分为数据类型关键字、控制结构关键字、存储类别关键字和其他关键字四大类,旨在帮助读者更好地理解和运用这些基本元素。C语言中共有32个关键字。 ... [详细]
  • 流处理中的计数挑战与解决方案
    本文探讨了在流处理中进行计数的各种技术和挑战,并基于作者在2016年圣何塞举行的Hadoop World大会上的演讲进行了深入分析。文章不仅介绍了传统批处理和Lambda架构的局限性,还详细探讨了流处理架构的优势及其在现代大数据应用中的重要作用。 ... [详细]
  • 汇编语言:编程世界的始祖,连C语言都敬畏三分!
    当C语言还在萌芽阶段时,它首次接触到了汇编语言,并对其简洁性感到震惊。尽管汇编语言的指令极其简单,但它却是所有现代编程语言的基础,其重要性不言而喻。 ... [详细]
author-avatar
mobiledu2502872123
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有