/*迪杰斯特拉算法算法步骤：
（1）初始时，S只包含源点。
（2）从U中选取一个距离v最小的顶点k加入S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中。
*/
#include
#include
#include
#define M 999
void main(){
int cost[6][6]={
{M,M,10,M,30,100},
{M,M,M, M, M,M },
{M,5,M, 50,M,M },
{M,M,M, M, M,10 },
{M,M,M, 20,M,60 },
{M,M,M, M, M,M }
};
typedef struct edge{
int adjvex; //边的一个顶点
int cost; //权值
}edge;
int total=0; //计数变量，计算共选择节点多少个
int adjvex[6];//保存依次被选中的节点
edge lowpathcost[6];//初始值为矩阵的第一行。
char path[6][10]={"0","","","","",""};//以0为初始节点开始计算最短路径 (路径)
for(int i=1;i
{ lowpathcost[i].cost=cost[0][i];//初始化为M，最短路径长度为矩阵的第一行权值
if(cost[0][i]!=M)
{
lowpathcost[i].adjvex=0;//有数据则adjvex置为0
cout
}
}
int min;//保存最小权值
int minvex;//保存最小权值边的另一顶点
int selected[6]={0};//次变量是作为控制已输出的节点不再参与的判断参数
cout
for(int num=1;num
{
min=M;
for(i=1;i
if(min>lowpathcost[i].cost&&!selected[i])
{
min=lowpathcost[i].cost;//第一次查找为10 即第一行中最小的值
minvex=i;//此时i=2
}
adjvex[++total]=minvex;//此时adjvex[1]为2，存放依次选出的顶点
//adjvex[2]=1
if(min!=M)
{
cout
}
selected[minvex]=1; //已参与的节点就置为1
for(i=0;i
if(!selected[i] && lowpathcost[i].cost>min+cost[minvex][i] && min+cost[minvex][i]
{
lowpathcost[i].cost=min+cost[minvex][i];
lowpathcost[i].adjvex=minvex;
}
}
for(i=1;i
cout
cout
int eadjvex,sadjvex;
char ep[2];
for(i=1;i
{
eadjvex=adjvex[i];
sadjvex=lowpathcost[eadjvex].adjvex;
ep[0]='0'+eadjvex; ep[1]='\0';
char tmp[10];
strcpy(tmp,path[sadjvex]);
strcpy(path[eadjvex],strcat(tmp,ep));// path[e]=sp+ep;
cout
athcost[eadjvex].cost
}
}
/*迪杰斯特拉算法算法步骤：
（1）初始时，S只包含源点。
（2）从U中选取一个距离v最小的顶点k加入S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中。
*/
#include
#include
#include
#define M 999
void main(){
int cost[6][6]={
{M,M,10,M,30,100},
{M,M,M, M, M,M },
{M,5,M, 50,M,M },
{M,M,M, M, M,10 },
{M,M,M, 20,M,60 },
{M,M,M, M, M,M }
};
typedef struct edge{
int adjvex; //边的一个顶点
int cost; //权值
}edge;
int total=0; //计数变量，计算共选择节点多少个
int adjvex[6];//保存依次被选中的节点
edge lowpathcost[6];//初始值为矩阵的第一行。
char path[6][10]={"0","","","","",""};//以0为初始节点开始计算最短路径 (路径)
for(int i=1;i
{ lowpathcost[i].cost=cost[0][i];//初始化为M，最短路径长度为矩阵的第一行权值
if(cost[0][i]!=M)
{
lowpathcost[i].adjvex=0;//有数据则adjvex置为0
cout
}
}
int min;//保存最小权值
int minvex;//保存最小权值边的另一顶点
int selected[6]={0};//次变量是作为控制已输出的节点不再参与的判断参数
cout
for(int num=1;num
{
min=M;
for(i=1;i
if(min>lowpathcost[i].cost&&!selected[i])
{
min=lowpathcost[i].cost;//第一次查找为10 即第一行中最小的值
minvex=i;//此时i=2
}
adjvex[++total]=minvex;//此时adjvex[1]为2，存放依次选出的顶点
//adjvex[2]=1
if(min!=M)
{
cout
}
selected[minvex]=1; //已参与的节点就置为1
for(i=0;i
if(!selected[i] && lowpathcost[i].cost>min+cost[minvex][i] && min+cost[minvex][i]
{
lowpathcost[i].cost=min+cost[minvex][i];
lowpathcost[i].adjvex=minvex;
}
}
for(i=1;i
cout
cout
int eadjvex,sadjvex;
char ep[2];
for(i=1;i
{
eadjvex=adjvex[i];
sadjvex=lowpathcost[eadjvex].adjvex;
ep[0]='0'+eadjvex; ep[1]='\0';
char tmp[10];
strcpy(tmp,path[sadjvex]);
strcpy(path[eadjvex],strcat(tmp,ep));// path[e]=sp+ep;
cout
athcost[eadjvex].cost
}
}