作者:mobiledu2502872123 | 来源:互联网 | 2023-10-11 12:53
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中。