数据结构与算法单源最短路径问题C++求解

#include
#include
using namespace std;
const int infinite = 16843009;
int ** matrix;
int num_point;
void menu();
void function(int choice);
void showMatrix();
void shortestPath(int source_point);
void showPath(int * finalDistance,int * finalPath,int source_point);
int main()
{
matrix = NULL;
num_point = 0;
menu();
int choice;
cin>>choice;
while (choice!=0)
{
function(choice);
menu();
cin>>choice;
}
return 0;
}
void menu()//菜单栏
{
cout<<"********************"<cout<<"1.建立有向网"<cout<<"2.求单元最短路径"<cout<<"3.退出"<cout<<"********************"<}
void function(int choice)//功能函数
{
if (choice==1)
{
int info[3];
cout<<"请输入顶点的个数："<cin>>num_point;
matrix = new int*[num_point];
for (int i=0;i{
matrix[i] = new int[num_point];
memset(matrix[i],1,num_point*sizeof(int));//赋初值为无穷大:16843009;
matrix[i][i] = 0;
}
cout<<"请按照三元组的形式输入各点信息（起点，终点，权值）"<cout<<"以(0,0,0)结束输入"<for (int i=0;i<3;i++)
{
cin>>info[i];
}
while (info[0]!=0)
{
matrix[info[0]-1][info[1]-1] = info[2];
for (int i=0;i<3;i++)
{
cin>>info[i];
}

}
cout<<"有向网建立成功:"<showMatrix();
}
else if (choice == 2)
{
int source_point;
cout<<"请输入您所选定的源点："<cin>>source_point;
shortestPath(source_point);

}
else if (choice == 3)
{
exit(0);
}
}
void shortestPath(int source_point)//求单源最短路
{
int *s = new int[num_point];//记录哪些点的最短路径已经确定
int * finalDistance = new int[num_point];//记录从源点到其他各点的最短长度
int * finalPath = new int[num_point];//记录最短长度对应的路径
memset(s,0,num_point*sizeof(int));//初始话s数组

for (int i=0;i{
finalDistance[i] = matrix[source_point-1][i];//初始化finalDistance数组
if (finalDistance[i]{
finalPath[i] = source_point-1;
}
else
{
finalPath[i] = infinite;
}

}
s[source_point-1] = 1;//源点到源点的最短距离已经确定

int max = infinite;
int prime = source_point-1;
int progress = 0;
while (progress < num_point-1)
{
max = infinite;
for (int i=0;i{
if (finalDistance[i]{
max = finalDistance

[i];
prime = i;
}
}

s[prime] = 1;
for (int i=0;i{
if (finalDistance[i]>finalDistance[prime] + matrix[prime][i])
{
finalDistance[i] = finalDistance[prime] + matrix[prime][i];
finalPath[i] = prime;
}
}
progress++;
}
//cout<<"ff"<showPath(finalDistance,finalPath,source_point);



}
void showPath(int * finalDistance,int * finalPath,int source_point)//输出单源最短路径
{
int k;
cout<<"单源最短路径为："<for (int i=0;i{

k = i;
cout<while (finalPath[k]!=source_point-1 && finalPath[k]!=infinite)
{
cout<k = finalPath[k];
}
cout<if (finalDistance[i]==infinite)
{
cout<<"∞"<}
else
{
cout<}
}
}
void showMatrix()//显示矩阵
{
for (int i=0;i{
for (int j=0;j{
if (matrix[i][j]==infinite)
{
cout<<"∞"<<"\t";
}
else
{
cout<}
}
cout<}
}