- C++语言实现；
- 有向图的存储结构为: 邻接矩阵；
- 这篇文章的代码是我根据B站UP主懒猫老师所写的，能成功运行，VS里面显示有很多警告。而且还可能存在有未调试出的BUG，请多多指教。
- 观看懒猫老师的视频后，才方便理解博主代码，不然可能理解起来会很吃力。
请前往B站观看 up主 懒猫老师 的教学视频;
——附:老师思路清楚，并且通过形象的PPT动画来模拟算法实现过程，非常有利于理解整个算法过程！
视频链接:
1.算法思想:
懒猫老师-数据结构-(46)最短路径(Dijkstra算法，迪杰斯特拉算法，单源最短路径)
2.算法实现过程:
懒猫老师-数据结构-(47)最短路径(Dijkstra算法实现，迪杰斯特拉算法，单源最短路径)
1.迪杰斯特拉算法函数；
void Dijkstra(AMGraph g)
{
int start;
char c;
cout << "请输入最小路径的源点:" << "t";
cin >> c;
start = g.Locate_vex(c); //利用定位函数查找源点在顶点表当中的序号；
//1.用动态分配的方式，为路径path， 路径权值dist, 算法思想中的S数组开辟空间。
//注意这里path，dist,S数组单元的序号所对应的顶点和类 AMGraph中顶点表 vexs 所对应的顶点是一样的！
int* path = new int[g.vexnum]; //空间大小为 图的顶点个数,vexnum;
int* dist = new int[g.vexnum];
int* S = new int[g.vexnum];
//2. 初始化这三个数组；
for (int i = 0; i < g.vexnum; i++)
{
dist[i] = g.arcs[start][i];
if (dist[i] != Maxlnt) path[i] = start;
else path[i] = -1;
}
for (int i = 0; i < g.vexnum; i++)
{
S[i] = 0; // 0代表未进入算法思想的S集合，1代表已经进入。
}
S[start] = 1; // 将源点加入S集合。
int num = 1; //计数变量，循环控制条件;
int min;
//3. 正式进入算法，求源点到其它顶点的最短路径。
while (num < g.vexnum)
{
min = findMinDist(dist, S, g.vexnum); //查找在当前顶点所邻接后继结点的边中，具有最小权值的后继结点的序号。
S[min] = 1;
for (int i = 0; i < g.vexnum; i++) //对路径数组path 和路径权值数组dist 进行更新。
{
if ((S[i] == 0) && (dist[i] > dist[min] + g.arcs[min][i]))
{
dist[i] = dist[min] + g.arcs[min][i];
path[i] = min;
}
}
num++;
}
displayPath(dist, path, start, g);
delete[]path;
delete[]dist;
delete[]S;
}
2.findMinDist()函数;
函数功能:
查找当前结点与后继邻接顶点中具有最小权值的边，的邻接顶点的序号
int findMinDist(int dist[], int S[], int n)
{
int MIN = Maxlnt + 1;
int mark = -1;
for (int i = 0; i < n; i++)
{
if (S[i] == 0)
{
if (dist[i] < MIN)
{
MIN = dist[i];
mark = i;
}
}
}
return mark;
}
3. 路径输出函数displayPath();
函数功能:
- 一、如果对于除了源点的其它顶点，如果源点是可达该顶点的，则输出其的最小路径和权值
- 二、输出源点所到达不了的顶点，说明这源点和这个顶点之间不存在有最短路径。
void displayPath(int dist[], int path[], int start, AMGraph g)
{
char* road = new char[g.vexnum];
int number; //number 用来表示源点到第i号顶点路径的长度；
for (int i = 0; i < g.vexnum; i++)
{
int j = i; //这里j可以从充当一个指针，一开始指向每条路径的终点。
if (j != start && dist[j] != Maxlnt) //注意这里j指向的终点必须是可达源点的，所以要加上判断条件 dist[j] 不可以等于无穷大 Maxlnt ;
{
number = -1;
//1.利用while循环，从最短路径的终点向源点逐步衍生，逐步扩大road数组
while (g.vexs[j] != g.vexs[start]) //当j 指向源点的时候，循环结束。
{
number++;
road[number] = g.vexs[j];
j = path[j]; //j指向当前顶点的，前驱邻接顶点。
if (j == start) //如果 j 指向源点了，将源点加入road 数组，数组中存储的就是逆序的路径了，number为路径的长度。
{
number++;
road[number] = g.vexs[j];
}
}
//2.利用for循环,将路径数组逆序输出即可得到 源点到第 i 号顶点的最小路径。
cout << endl << g.vexs[start] << " to " << g.vexs[i] << " " << "路径权值:" << dist[i] << "t" << "路径为: ";
for (int k = number; k >= 0; k--)
{
if (k == 0)
{
cout << road[k] << endl;
}
else cout << road[k] << "—>";
}
cout << endl;
}
}
//3.布尔变量adjust, 用来判断源点是否有到达不了的顶点, 如果有则利用for循环输出。
bool adjust = true;
for (int i = 0; i < g.vexnum; i++)
{
if (dist[i] == Maxlnt)
{
adjust = false;
break;
}
}
if (adjust == false)
{
cout << endl << "源点:" << g.vexs[start] << "到达不了的顶点为:" << "t";
for (int i = 0; i < g.vexnum; i++)
{
if (dist[i] == Maxlnt)
cout << g.vexs[i] << "t";
}
cout << endl << endl;
}
delete[]road;
}
四、完整代码:
说明: 为了更方便地调试程序，我将算法具体实现写成了一个小小系统的形式，
所以代码会比较冗长，注释也比较多，阅读起来可能很不舒适。
#include五、测试情况:#include using namespace std; #define Maxlnt 32767 #define MVNum 20 #define OK 1 class AMGraph { private: char vexs[MVNum]; //顶点表; int arcs[MVNum][MVNum]; //边表; int vexnum, arcnum; //点的数量和边的数量; public: bool creat_graph(); int Locate_vex(char c); //顶点定位函数,定位顶点在顶点表当中的数字； void print(); // 图的信息打印函数; friend void displayPath(int dist[], int path[], int start, AMGraph g); // 路径输出函数; friend void Dijkstra(AMGraph g); }; int AMGraph::Locate_vex(char c) { for (int i = 0; i < vexnum; i++) { if (c == vexs[i]) return i; } return -1; } bool AMGraph::creat_graph() { cout << "请依次输入图的顶点数目和边数:" << "t"; cin >> vexnum >> arcnum; cout << endl << "请依次输入" << vexnum << "个顶点:" << "t"; for (int i = 0; i < vexnum; i++) { cin >> vexs[i]; } for (int i = 0; i < vexnum; i++) { for (int j = 0; j < vexnum; j++) { if (i == j) arcs[i][j] = 0; else arcs[i][j] = Maxlnt; } } cout << endl; for (int k = 0; k < arcnum; k++) { char v1, v2; int w; cout << "请分别输入第" << k + 1 << "条有向边的起点，终点和权值:" << "t"; cin >> v1 >> v2 >> w; int i = Locate_vex(v1); int j = Locate_vex(v2); arcs[i][j] = w; } return OK; } void AMGraph::print() { cout << endl << "顶点表的信息:" << endl; for (int i = 0; i < vexnum; i++) { cout << vexs[i] << " "; } cout << endl << endl; cout << "邻接矩阵的信息为:" << endl; // 这里for循环 从-1 开始打印邻接矩阵表格; for (int i = -1; i < vexnum; i++) { for (int j = -1; j < vexnum; j++) { //i=-1的时候, 需要输出边表中, 以i为起点的边所对应的终点; if (i == -1) { if (j == -1)cout << " " << "t"; else cout << vexs[j] << "t"; if (j == vexnum - 1) //换行条件控制 cout << endl; } else { //j=-1的时候，需要输出边表中, 以j为终点的边所对应的起点: if (j == -1)cout << vexs[i] << "t"; else { if (arcs[i][j] == Maxlnt) cout << "∞" << "t"; else cout << arcs[i][j] << "t"; if (j == vexnum - 1) //换行条件控制 cout << endl; } } } } } int findMinDist(int dist[], int S[], int n) { int MIN = Maxlnt + 1; int mark = -1; for (int i = 0; i < n; i++) { if (S[i] == 0) { if (dist[i] < MIN) { MIN = dist[i]; mark = i; } } } return mark; } void displayPath(int dist[], int path[], int start, AMGraph g) { char* road = new char[g.vexnum]; int number; //number 用来表示源点到第i号顶点路径的长度； for (int i = 0; i < g.vexnum; i++) { int j = i; //这里j可以从充当一个指针，一开始指向每条路径的终点。 if (j != start && dist[j] != Maxlnt) //注意这里j指向的终点必须是可达源点的，所以要加上判断条件 dist[j] 不可以等于无穷大 Maxlnt ; { number = -1; //1.利用while循环，从最短路径的终点向源点逐步衍生，逐步扩大road数组 while (g.vexs[j] != g.vexs[start]) //当j 指向源点的时候，循环结束。 { number++; road[number] = g.vexs[j]; j = path[j]; //j指向当前顶点的，前驱邻接顶点。 if (j == start) //如果 j 指向源点了，将源点加入road 数组，数组中存储的就是逆序的路径了，number为路径的长度。 { number++; road[number] = g.vexs[j]; } } //2.利用for循环,将路径数组逆序输出即可得到 源点到第 i 号顶点的最小路径。 cout << endl << g.vexs[start] << " to " << g.vexs[i] << " " << "路径权值:" << dist[i] << "t" << "路径为: "; for (int k = number; k >= 0; k--) { if (k == 0) { cout << road[k] << endl; } else cout << road[k] << "—>"; } cout << endl; } } //3.布尔变量adjust, 用来判断源点是否有到达不了的顶点, 如果有则利用for循环输出。 bool adjust = true; for (int i = 0; i < g.vexnum; i++) { if (dist[i] == Maxlnt) { adjust = false; break; } } if (adjust == false) { cout << endl << "源点:" << g.vexs[start] << "到达不了的顶点为:" << "t"; for (int i = 0; i < g.vexnum; i++) { if (dist[i] == Maxlnt) cout << g.vexs[i] << "t"; } cout << endl << endl; } delete[]road; } void Dijkstra(AMGraph g) { int start; char c; cout << "请输入最小路径的源点:" << "t"; cin >> c; start = g.Locate_vex(c); //利用定位函数查找源点在顶点表当中的序号； //1.用动态分配的方式，为路径path， 路径权值dist, 算法思想中的S数组开辟空间。 //注意这里path，dist,S数组单元的序号所对应的顶点和类 AMGraph中顶点表 vexs 所对应的顶点是一样的！ int* path = new int[g.vexnum]; //空间大小为 图的顶点个数,vexnum; int* dist = new int[g.vexnum]; int* S = new int[g.vexnum]; //2. 初始化这三个数组； for (int i = 0; i < g.vexnum; i++) { dist[i] = g.arcs[start][i]; if (dist[i] != Maxlnt) path[i] = start; else path[i] = -1; } for (int i = 0; i < g.vexnum; i++) { S[i] = 0; // 0代表未进入算法思想的S集合，1代表已经进入。 } S[start] = 1; // 将源点加入S集合。 int num = 1; //计数变量，循环控制条件; int min; //3. 正式进入算法，求源点到其它顶点的最短路径。 while (num < g.vexnum) { min = findMinDist(dist, S, g.vexnum); //查找在当前顶点所邻接后继结点的边中，具有最小权值的后继结点的序号。 S[min] = 1; for (int i = 0; i < g.vexnum; i++) //对路径数组path 和路径权值数组dist 进行更新。 { if ((S[i] == 0) && (dist[i] > dist[min] + g.arcs[min][i])) { dist[i] = dist[min] + g.arcs[min][i]; path[i] = min; } } num++; } displayPath(dist, path, start, g); delete[]path; delete[]dist; delete[]S; } void menu() { cout << "****《迪杰斯特拉算法求最短路径》*****" << endl; cout << "**1. 图的建立" << endl; cout << "**2. 输出图的信息" << endl; cout << "**3. 求图的最短路径" << endl; cout << "**4. 退出" << endl; cout << "____________________________________________" << endl; } void deletescreen() { system("pause"); system("cls"); } int main() { void menu(); void deletescreen(); AMGraph g1; //menu(); string choose; while (true) { menu(); cin >> choose; if (choose == "1") { g1.creat_graph(); cout << endl << "图建立成功！" << endl; deletescreen(); } else if (choose == "2") { g1.print(); deletescreen(); } else if (choose == "3") { Dijkstra(g1); deletescreen(); } else if (choose == "4") { cout << "退出成功！" << endl; exit(0); } else { cout << "输入有误！请重新输入" << endl; deletescreen(); } } return 0; }
测试一:
求图片中
1.源点为A到其它顶点的最小路径
2.源点为D到其它顶点的最小路径
测试结果:
1.建图
2.图的信息:
3.A到其它顶点的最小路径
4.D到其它顶点的最小路径
测试二:
1.测试案例:
2.求以 0 作为源点，到其它顶点的最短路径:
感谢你的收看，希望这可以帮助到你。
