今天是小学期的第一天,也是数据结构小学期的第一天,今天老师说明了第一阶段的任务,五人成组,每个组员四道题,共20道题,我的四道题是最短路径(迪杰斯特拉算法)、希尔排序的实现、先序和中序构造二叉树 、矩阵运算,今天完成了第一道题最短路径(迪杰斯特拉算法),以下是题目要求
试实现迪杰斯特拉最短路径算法。
函数接口定义:
void ShortestPath_DIJ(AMGraph G, int v0);
其中 G
是基于邻接矩阵存储表示的有向图, v0
表示源点
裁判测试程序样例:
#include <iostream>
using namespace std;
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
int *D=new int[MVNum];
bool *S=new bool[MVNum];
int *Path=new int[MVNum];
typedef struct{
VerTexType vexs[MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;
void CreateUDN(AMGraph &G){
int i , j , k;
cin >> G.vexnum >> G.arcnum;
for(i = 0; i < G.vexnum; ++i){
cin >> G.vexs[i];
}
for(i = 0; i < G.vexnum; ++i)
for(j = 0; j < G.vexnum; ++j)
G.arcs[i][j] = MaxInt;
for(k = 0; k < G.arcnum;++k){
VerTexType v1 , v2;
ArcType w;
cin >> v1 >> v2 >> w;
i = LocateVex(G, v1);
j = LocateVex(G, v2);
G.arcs[i][j] = w;
G.arcs[j][i] = G.arcs[i][j];
}
}
void ShortestPath_DIJ(AMGraph G, int v0);
void DisplayPath(AMGraph G , int begin ,int temp ){
if(Path[temp] != -1){
DisplayPath(G , begin ,Path[temp]);
cout << G.vexs[Path[temp]] << "->";
}
}
int main()
{
AMGraph G;
int i , j ,num_start , num_destination;
VerTexType start , destination;
CreateUDN(G);
cin >> start >> destination;
num_start = LocateVex(G , start);
num_destination = LocateVex(G , destination);
ShortestPath_DIJ(G , num_start);
DisplayPath(G , num_start , num_destination);
cout << G.vexs[num_destination]<<endl;
return 0;
}
/* 请在这里填写答案 */
输入样例:
第1行输入结点数vexnum和边数arcnum。第2行输入vexnum个字符表示结点的值,接下来依次输入arcnum行,每行输入3个值,前两个字符表示结点,后一个数表示两个结点之间边的权值。最后一行输入源点及终点。
6 8
012345
0 5 100
0 2 10
0 4 30
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
0 5
输出样例:
输出源点到终点的最短路径。
0->4->3->5
我的代码:
void ShortestPath_DIJ(AMGraph G, int v0) {
// 初始化
for (int i = 0; i < G.vexnum; ++i) {
D[i] = G.arcs[v0][i]; // 从v0到各顶点的初始路径长度
S[i] = false; // 标记数组,表示顶点是否已加入最短路径树
if (i != v0 && D[i] < MaxInt) {
Path[i] = v0; // 如果存在直接路径,则设置路径的起点为v0
} else {
Path[i] = -1; // 无路径时设为-1
}
}
D[v0] = 0;
S[v0] = true; // 将源点v0加入最短路径树
// 迪杰斯特拉算法核心
for (int i = 1; i < G.vexnum; ++i) {
int min = MaxInt;
int k = v0;
// 选择当前路径长度最小的顶点
for (int j = 0; j < G.vexnum; ++j) {
if (!S[j] && D[j] < min) {
min = D[j];
k = j;
}
}
S[k] = true; // 将顶点k加入最短路径树
// 更新从顶点k出发可以到达的所有顶点的最短路径长度
for (int j = 0; j < G.vexnum; ++j) {
if (!S[j] && G.arcs[k][j] < MaxInt) {
if (D[k] + G.arcs[k][j] < D[j]) {
D[j] = D[k] + G.arcs[k][j];
Path[j] = k; // 更新路径信息
}
}
}
}
}