图的最短路径——DIJ算法，有向图的矩阵实现，图的基本操作 _最短路径

图是一种非常重要的数据结构，在研究从一点出发到各个顶点的最短距离。
实验目的
1. 掌握图的基本概念、表示方法、遍历方法。
2. 掌握图的最短路径算法。
实验要求
1．输入图的顶点数n（不超过10个）、边数m，顶点分别用0到n-1表示；
2．采用“起始顶点，终止顶点，权值”输入图的m条边，创建图；
3．输出从顶点0开始的BFS遍历、DFS遍历的顶点遍历顺序；
4．输出从顶点0到其余顶点最短路径及最短路径的长度，如果没有路经，输出0 。

文章插图
程序实现
主程序

int main() {int n, m,point1,point2,weight;cout << "\n请输入顶点n数,边数m值\n";cin >> n >> m;cout << "请输入起始顶点，终止顶点，权值，顶点范围[0 n-1]\n";cout << "形如 0 4 6\n";CreatMap(n, m);cout << "\n广度遍历 BFS\n";BFS(map);cout << "\n深度遍历 DFS\n";DFS(map);ShortestPath_DIJ(map, 0);cout << "\nMap";return 0;}

1，2 输入图的顶点数n（不超过10个）、边数m，顶点分别用0到n-1表示；
创建有向图

//creat map#define INFINITY 100000#define MAX_VERTEX_NUM 10 //最大顶点数typedef struct {int vexs[MAX_VERTEX_NUM];int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int vexnum, arcnum;}MGraph;MGraph map;//创建图void CreatMap(int n, int m) {map.vexnum = n;map.arcnum = m;int i, j, w;for (i = 0; i < n; i++)map.vexs[i] = i ;for (i = 0; i < n; i++)for (j = 0; j < n; j++)map.arcs[i][j] = INFINITY;for (int k = 1; k <= m; k++) {//想依次输入可添加下面一行；//cout << "请输入第"<> i >> j >> w;if(i

遍历

深度遍历——DFS

int DFSvisited[10];void DFS(MGraph m,int v) {cout << m.vexs[v]<<"";DFSvisited[v] = -1;int w;for (w = 0; w < m.vexnum; w++) {if (DFSvisited[w] != -1&&m.arcs[v][w] != INFINITY)DFS(m, w);}}void DFS(MGraph m) {for (int i=0; i < 10; i++)DFSvisited[i] = i;for (int i = 0; i < m.vexnum; i++)if(DFSvisited[i] != -1)DFS(m, i);}

BFS

void BFS(MGraph m) {int visited[10];for (int i = 0; i < 10; i++) {visited[i] = 1;}queue Q;for (int v = 0; v < m.vexnum; v++) {if (visited[v] == 1) {visited[v] = -1;cout << m.vexs[v]<<"";Q.push(v);while (!Q.empty()) {int u;u = Q.front();Q.pop();for (int w = 0; w < m.vexnum; w++) {if (visited[w] == 1&&m.arcs[u][w]!=INFINITY) {cout << m.vexs[w] << "";visited[w] = -1;Q.push(w);}}}}}}

从一点出发最短路径

void ShortestPath_DIJ(MGraph G, int V0) {int P[10][10], D[10],final[10], v, w;int path[10][10];for ( v = 0; v < G.vexnum; v++) {final[v] = 0;D[v] = G.arcs[V0][v];for ( w = 0; w < G.vexnum; w++) {P[v][w ] = 0;path[v][w] = -1;}if (D[v] < INFINITY) {P[v][V0] = 1;P[v][v] = 1;path[v][0] = 0;path[v][1] = v;}}D[V0] = 0;final[V0] = 1;for (int i = 1; i < G.vexnum; i++) {int min = INFINITY;int minpath[10];for ( w = 0; w < G.vexnum; w++) {if(final[w]==0)if (D[w] < min) {v = w;min = D[w];for (int k = 0; k < 10; k++)minpath[k] = path[v][k];}}final[v] = 1;for (w = 0; w < G.vexnum; w++) {if ((final[w] == 0) && ((min + G.arcs[v][w]) < D[w])) {D[w] = min + G.arcs[v][w];int k;for (k = 0; minpath[k] != -1; k++)path[w][k] = path[v][k];path[w][k] = w;for (int i = 0; i < G.vexnum; i++) {P[w][i] = P[v][i];}P[w][w] = 1;}}}

测试：

???????

总程序：

【图的最短路径——DIJ算法，有向图的矩阵实现，图的基本操作】#include#include#includeusing namespace std;/*1． 输入图的顶点数n（不超过10个）、边数m，顶点分别用0到n-1表示；2． 采用“起始顶点，终止顶点，权值”输入图的m条边，创建图；3． 输出从顶点0开始的BFS遍历、DFS遍历的顶点遍历顺序；4． 输出从顶点0到其余顶点最短路径及最短路径的长度，如果没有路经，输出0 。*///creat map#define INFINITY 100000#define MAX_VERTEX_NUM 10 //最大顶点数typedef struct {int vexs[MAX_VERTEX_NUM];int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int vexnum, arcnum;}MGraph;MGraph map;void BFS(MGraph m) {int visited[10];for (int i = 0; i 
上一页
1
2
下一页
		  	









如何把excel表的联系方式导入到手机 

六  Linux：系统运维常用命令 

完整的ResNet代码 

香榧种植的注意事项 

2  FPGA实现SPI接口--SPI接口芯片的实际使用 

3  面向监狱编程- 石胖子写网游外挂 图片识别 

冯.诺伊曼结构、哈佛结构、超级哈佛结构之间的异同 

【精品】pinia 基于插件pinia-plugin-persist的 持久化 

1800年前是什么朝代 

1850年是什么朝代