赞
踩
在代码中有其他需求可自行按备注更改,本代码是学校实验任务,参照课本及网上资料以及自己更改编写完成。
实验内容:输入图的顶点数、边数以及边,求某个顶点到各个顶点的最短路径。
该实验中输入的v0点即为要求的某个顶点,在输入顶点字符信息的地方,只是简单的将字符信息转换为数字信息,在代码中还可对其进行优化。
1、picture.cpp文件
- #define _CRT_SECURE_NO_WARNINGS 1
-
- #include <stdio.h>
- #include <iostream>
- #include <sstream>
- #include <string>
- #include "picture.h"
-
- using namespace std;
-
- Status LocateVex(AMGraph G, VerTexType u)
- {
- int i;
- for (i = 0; i < G.vexnum; ++i)
- {
- if (G.vexs[i] == u)
- return i; // 找到顶点值为u的位置,返回该位置在顶点表中的索引 i
- }
- return ERROR; // 没找到,返回错误码
- }
-
- Status CreateDN(AMGraph& G) //采用邻接矩阵表示法,创建有向网G
- {
- int i, j, k, w;
- VerTexType v1, v2; //v1、v2表示点的位置、w表示该点权值
- cout << "输入总顶点数:";
- cin >> G.vexnum; //输入总顶点数、总边数
- cout << "输入总边数:";
- cin >> G.arcnum;
-
- cout << "依次输入顶点名称:";
- for (i = 0; i < G.vexnum; ++i) //依次输入点的信息
- cin >> G.vexs[i];
-
- for (i = 0; i < G.vexnum; ++i) //初始化邻接矩阵、边的权值 均置为极大值MaxInt
- for (j = 0; j < G.vexnum; ++j)
- G.arcs[i][j] = MaxInt;
-
- for (k = 0; k < G.arcnum; ++k) //构建邻接矩阵
- {
- cout << "输入一条边的起点、终点及权值:";
- cin >> v1 >> v2 >> w; //输入一条边依附的顶点及权值
- i = LocateVex(G, v1);
- j = LocateVex(G, v2); //确定v1、v2在G中的位置,即顶点数组下标
- if (i == ERROR || j == ERROR)
- {
- cout << "顶点不存在!" << endl;
- return ERROR;
- }
- G.arcs[i][j] = w; //边<v1,v2>的权值置为w 对称边<v2,v1>的权值为w
- }
- return OK;
- }
- //用Dijkstra算法求有向网的v0顶点到其余顶点的最短路径
- void ShortestPath_DIJ(AMGraph G, int v0, int *D, int *Path)
- {
- int n, v, i, min, w, max, m;
- int S[20];
- n = G.vexnum; //n为G中顶点的个数
- for (v = 0; v < n; ++v) //n个顶点依次初始化
- {
- S[v] = false; //S初始为空集
- D[v] = G.arcs[v0][v]; //将v0到各个终点的最短路径长度初始化为弧上的权值
- if (D[v] < MaxInt) //如果v0和v之间有弧,则将v的前驱置为v0
- Path[v] = v0;
- else //如果v0和v之间无弧,则将v的前驱置为-1
- Path[v] = -1;
- }
- S[v0] = true; //将v0加入S
- D[v0] = 0; //源点到源点的距离为0
- /*-----初始化结束,开始主循环,每次求得v0到某个顶点v的最短路径,将v加到S集-----*/
- for (i = 1; i < n; ++i) //对其余n-1个顶点,依次进行计算
- {
- min = MaxInt;
- for (w = 0; w < n; ++w)
- if (!S[w] && D[w] < min)
- {
- v = w;
- min = D[w]; //选择一条当前的最短路径,终点为v
- }
- S[v] = true; //将v加入S
- for (w = 0; w < n; ++w) //更新从v0出发到集合V-S上所有顶点的最短路径长度
- if (!S[w] && (D[v] + G.arcs[v][w] < D[w]))
- {
- D[w] = D[v] + G.arcs[v][w]; //更新D[w]
- Path[w] = v; //更新w的前驱为v
- }
- }
- }
2、picture.h文件
- #pragma once
- #ifndef PICTURE_H
- #define PICTURE_H
-
- typedef int Status;
- #define OK 1
- #define ERROR -1
-
- #define swap(a, b) {a = a + b; b = a - b; a = a - b;}
-
- //-------图的邻接矩阵存储表示--------//
- #define MaxInt 32767 //表示极大值,即∞
- #define MVNum 100 //最大顶点数
- typedef char VerTexType; //假设顶点的数据类型为字符型
- typedef int ArcType; //假设边的权值类型为整型
- typedef struct
- {
- VerTexType vexs[MVNum]; //顶点表
- ArcType arcs[MVNum][MVNum]; //邻接矩阵
- int vexnum, arcnum; //图的当前点数和边数
- }AMGraph;
-
- Status CreateDN(AMGraph& G); //采用邻接矩阵表示法,创建有向网G
- Status LocateVex(AMGraph G, VerTexType u);
- void ShortestPath_DIJ(AMGraph G, int v0, int* D, int* Path);
-
- #endif
3、main.cpp文件
- #define _CRT_SECURE_NO_WARNINGS 1
-
- #include <iostream>
- #include <iomanip>
- #include "picture.h"
-
- using namespace std;
-
- void show(AMGraph G, int* D, int* Path)
- {
- for (int i = 0; i < G.vexnum; ++i)
- {
- if (D[i] == MaxInt)
- {
- cout << "从v0到 " << G.vexs[i] << " 点的路径不存在" << endl;
- }
- else
- {
- cout << "从v0到 " << G.vexs[i] << " 点的最短路径为:" << G.vexs[i];
- int pre = Path[i];
- while (pre != -1)
- {
- cout << " <- " << G.vexs[pre];
- pre = Path[pre];
- }
- cout << ",长度为:" << D[i] << endl;
- }
- }
- }
-
- int main()
- {
- int D[10];
- int Path[20];
- AMGraph G;
- CreateDN(G);
- cout << "v0到各点的最短路径(输入v0):";
- int v0;
- char v01;
- cin >> v01;
- for (v0 = 0; v0 < G.vexnum; ++v0)
- {
- if (G.vexs[v0] == v01)
- break;
- }
- ShortestPath_DIJ(G, v0, D, Path);
- show(G, D, Path);
- return 0;
- }
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。