C语言实现Dijkstra算法


-
本程序使用C语言实现了Dijkstra算法。程序中,定义好邻接矩阵,可以计算出任一节点到其他所有节点的最短路径,并打印路径与长度。其中对最短路径的存储是依据所得到的生成树,可以减少内存空间占用。
C 语言 实现Dijkstra算法_course
2017-05-17怎么把这个程序中的数组写在文件里再用文件读取 #include <stdio.h> #include <stdlib.h> #include <io.h> #include <math.h> #include <time.h> #include <fstream> #include <string> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXEDgE 20 #define MAXVEX 20 #define INFINITY 65535 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef struct { int vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; }Mgraph; typedef int Patharc[MAXVEX]; /* 用于存储最短路径下标的数组 */ typedef int ShortPathTable[MAXVEX]; /* 用于存储到各点最短路径的权值和 */ void CreateMgraph(Mgraph *g) { int i, j; /* printf("请输入边数和顶点数:"); */ g->numEdges=16; g->numVertexes=9; for (i = 0; i < g->numVertexes; i++)/* 初始化图 */ { g->vexs[i]=i; } for (i = 0; i < g->numVertexes; i++)/* 初始化图 */ { for ( j = 0; j < g->numVertexes; j++) { if (i==j) g->arc[i][j]=0; else g->arc[i][j] = g->arc[j][i] = INFINITY; } } //这里怎么改成从文件里读取 g->arc[0][1]=1; g->arc[0][2]=5; g->arc[1][2]=3; g->arc[1][3]=7; g->arc[1][4]=5; g->arc[2][4]=1; g->arc[2][5]=7; g->arc[3][4]=2; g->arc[3][6]=3; g->arc[4][5]=3; g->arc[4][6]=6; g->arc[4][7]=9; g->arc[5][7]=5; g->arc[6][7]=2; g->arc[6][8]=7; g->arc[7][8]=4; for(i = 0; i < g->numVertexes; i++) { for(j = i; j < g->numVertexes; j++) { g->arc[j][i] =g->arc[i][j]; } } } /* Dijkstra算法,求有向网g的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */ /* P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */ void ShortestPath_Dijkstra(Mgraph g, int v0, Patharc *P, ShortPathTable *D) { int v,w,k,min; int final[MAXVEX]; /* final[w]=1表示求得顶点v0至vw的最短路径 */ /* 初始化数据 */ for(v=0; v<g.numVertexes; v++) { final[v] = 0; /* 全部顶点初始化为未知最短路径状态 */ (*D)[v] = g.arc[v0][v]; /* 将与v0点有连线的顶点加上权值 */ (*P)[v] = 0; /* 初始化路径数组P为0 */ } (*D)[v0] = 0; /* v0至v0路径为0 */ final[v0] = 1; /* v0至v0不需要求路径 */ /* 开始主循环,每次求得v0到某个v顶点的最短路径 */ for(v=1; v<g.numVertexes; v++) { min=INFINITY; /* 当前所知离v0顶点的最近距离 */ for(w=0; w<g.numVertexes; w++) /* 寻找离v0最近的顶点 */ { if(!final[w] && (*D)[w]<min) { k=w; min = (*D)[w]; /* w顶点离v0顶点更近 */ } } final[k] = 1; /* 将目前找到的最近的顶点置为1 */ /* 修正当前最短路径及距离 */ for(w=0; w<g.numVertexes; w++) { /* 如果经过v顶点的路径比现在这条路径的长度短的话 */ if(!final[w] && (min+g.arc[k][w]<(*D)[w])) { /* 说明找到了更短的路径,修改D[w]和P[w] */ (*D)[w] = min + g.arc[k][w]; /* 修改当前路径长度 */ (*P)[w]=k; } } } } int main(void) { int i,j,v0; Mgraph g; Patharc P; ShortPathTable D; /* 求某点到其余各点的最短路径 */ v0=0; CreateMgraph(&g); ShortestPath_Dijkstra(g, v0, &P, &D); printf("最短路径倒序如下:\n"); for(i=1;i<g.numVertexes;++i) { printf("v%d - v%d : ",v0,i); j=i; while(P[j]!=0) { printf("%d ",P[j]); j=P[j]; } printf("\n"); } printf("\n源点到各顶点的最短路径长度为:\n"); for(i=1;i<g.numVertexes;++i) printf("v%d - v%d : %d \n",g.vexs[0],g.vexs[i],D[i]); return 0; }
26KB
Dijkstra算法_C语言实现代码
2011-12-24能够实现 Dijkstra算法,内涵代码,运行即可实现
2KB
C例子:最短路径(dijkstra算法)
2015-10-07该程序是我写的博客“一起talk C栗子吧(第五十四回:C语言实例--图的最短路径二)”的配套程序,共享给大家使用
Dijkstra算法C代码实现下载_course
2019-07-10Dijkstra算法C代码实现,处理输入文件,生成最短路径并输出。谨供参考。 相关下载链接://download.csdn.net/download/icymoon/2968000?utm_sourc
1KB
c语言实现dijkstra算法源代码
2018-12-10最短路径问题是图论研究中的一个经典算法问题,旨在寻找图中两结点之间的最短路径。算法具体的形式包括: 确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。适合使用Dijkstra算法。包括图的
3KB
Dijkstra算法的C语言实现
2008-12-04刚学了一种不错的算法——Dijkstra,既简单又实用,呵呵,传上来希望对大家能有所帮助
c语言实现dijkstra算法源代码下载_course
2018-12-10最短路径问题是图论研究中的一个经典算法问题,旨在寻找图中两结点之间的最短路径。算法具体的形式包括: 确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。适合使用Dijkstra算法。包括图的
-
下载
武汉理工大学机械原理复习.pdf
武汉理工大学机械原理复习.pdf
-
博客
PHP内核在线客服系统源码多商户版
PHP内核在线客服系统源码多商户版
-
下载
长春理工大学《操作系统》3套期末考试试卷(含答案).pdf
长春理工大学《操作系统》3套期末考试试卷(含答案).pdf
-
下载
10款DesignSpark PCB 6.0 设计的Arduino板原理图PCB文件.zip
10款DesignSpark PCB 6.0 设计的Arduino板原理图PCB文件.zip
-
下载
fpga高手做过的例程,包括完整的项目
fpga高手做过的例程,包括完整的项目
-
博客
Python.牛客.HJ13.句子逆序
Python.牛客.HJ13.句子逆序
-
学院
C# 高级网络编程及RRQMSocket框架详解
C# 高级网络编程及RRQMSocket框架详解
-
学院
PowerBI重要外部工具详解
PowerBI重要外部工具详解
-
博客
一键部署H5即时通讯/带群聊/可封装APP
一键部署H5即时通讯/带群聊/可封装APP
-
下载
西方经济学(微观部分)第五版课后习题答案.pdf
西方经济学(微观部分)第五版课后习题答案.pdf
-
学院
C和C++课程
C和C++课程
-
学院
朱老师鸿蒙系列课程第1期-2鸿蒙系统Harmonyos源码架构分析
朱老师鸿蒙系列课程第1期-2鸿蒙系统Harmonyos源码架构分析
-
博客
service指令
service指令
-
下载
第二章 Profibus现场总线通信系统的组建.pptx
第二章 Profibus现场总线通信系统的组建.pptx
-
下载
武汉理工大学《机械原理》期末考试试卷(含答案).pdf
武汉理工大学《机械原理》期末考试试卷(含答案).pdf
-
学院
《Linux 命令简介》<Linux核心命令系列Series> <1.
《Linux 命令简介》<Linux核心命令系列Series> <1.
-
下载
draw.io-arm64-14.4.3.dmg
draw.io-arm64-14.4.3.dmg
-
学院
牛牛量化策略交易
牛牛量化策略交易
-
学院
MySQL 设计基础(数据库概论、初探)
MySQL 设计基础(数据库概论、初探)
-
下载
spnc034.zip
spnc034.zip
-
下载
9-Verilog HDL四则运算设计.7z
9-Verilog HDL四则运算设计.7z
-
博客
动态存储区、静态存储区、堆和栈的区别
动态存储区、静态存储区、堆和栈的区别
-
下载
C#直接发送打印机命令到打印机
C#直接发送打印机命令到打印机
-
博客
给头像加上圣诞帽子源码
给头像加上圣诞帽子源码
-
博客
【ACWing】1058. 股票买卖 V
【ACWing】1058. 股票买卖 V
-
博客
docker安装成功
docker安装成功
-
下载
汇编语言基础 .ppt
汇编语言基础 .ppt
-
博客
PHP在线自动发卡网源码 一键安装版
PHP在线自动发卡网源码 一键安装版
-
下载
武汉理工大学《机械原理》期末复习试题(含答案).pdf
武汉理工大学《机械原理》期末复习试题(含答案).pdf
-
下载
中山大学《结构化学》历年期中考试试卷(含答案).pdf
中山大学《结构化学》历年期中考试试卷(含答案).pdf