迪吉斯特算法

迪吉斯特算法

迪吉斯特算法每次寻找最小权重

展示一下流程：

假设有向连通图是这一个,它有6个顶点分别是ABCDEF,8条路径

AF,AE,AC,BC,CD,DF,ED,EF：

256表示没连通，剩下的则是路径权重

1：初始化

my_final[0]=true;

D[]=开始点所在行的路径权重，也就是第一行//自己距离自己所以D[0]=0

2.因为上图中D[2]最小，所以把AC并入，变成下表：

AC并入后，标记为已经由起点A到达C,所以final[2]=true;

并根据上面的邻接矩阵图寻找第三行,也就是顶点C与哪些顶点有相连

由图知道与D相连，发现D的下标3，final[3]等于false，并且由A经过C到D的路径长度10+50<256(无穷)

所以更改其值，如下表：

3.重复2的步骤，寻找表中最小且是false的；

上面的步骤可以找到最短路径长度，但是我们还需要知道是怎么走，路径最短的；

所以需要使用一个二维数组，帮我们记下

也就是程序中的Path  P；//注意P是一个二维数组的地址,bool类型

例如上面举的栗子：由A经过C到D

就记录P[3][j]=P[2][j]//注释：j是0到顶点数的所有值；

并且把P[3][3]=true;

更详细的注释在程序里面，剩下的就不罗嗦了

/*
迪吉斯特算法
最短路径
typedef int  数组
*/
#include <malloc.h>
#include <iostream>
#include <cstdio>
using namespace std;
#define  MAX_LEN    20//图最大顶点数
#define  INFINITY   255
typedef  bool       Path[MAX_LEN][MAX_LEN];
typedef  int        short_table[MAX_LEN];//定义一个short_table类型
//short_table  D  ==>>   int D[MAX_LEN]
typedef  struct  graph
{int vexnum,arcnum;int tyust[MAX_LEN][MAX_LEN];char vex[MAX_LEN];
}*Graph;
void  DIJ_shortestpath(Graph G,int v0,Path P,short_table D)
{bool  my_final[MAX_LEN];int my_min;int v;//辅助数组final和D初始化for(int i=0;i<G->vexnum;i++){my_final[i]=false;D[i]=G->tyust[v0][i];for(int w=0;w<G->vexnum;w++){P[i][w]=false;//初值为0，没有路径}if(D[i]<INFINITY){P[i][v0]=P[i][i]=true;//初始化传入顶点(0,也就是首列)那一列//把对角线置1，为了下面记录经过了哪些顶点}}D[v0]=0;my_final[v0]=true;for(int i=1;i<G->vexnum;i++)//剩余的顶点{my_min=INFINITY;for(int w=0;w<G->vexnum;w++)//寻找D中最小值{if(!my_final[w]&&D[w]<my_min){my_min=D[w];v=w;}}my_final[v]=true;//标志已经到达//所有最小的加起来就是最小的for(int w=0;w<G->vexnum;w++)//新并入之后，替换{if(!my_final[w]&&my_min<INFINITY&&G->tyust[v][w]<INFINITY&&(my_min+G->tyust[v][w]<D[w]))//未标记，存在最小值，存在下一个连接点，连接点距离小于目前的距离//可以优化的{D[w]=my_min+G->tyust[v][w];//替换成最小值for(int j=0;j<G->vexnum;j++){P[w][j]=P[v][j];//记录P[w][w]=true;}}}}
}int get_pos(Graph my_map,char c)
{for(int i=0;i<my_map->vexnum;i++){if(my_map->vex[i]==c){return i;}}return -1;
}
void print(Graph my_map)
{for(int i=0;i<my_map->vexnum;i++){for(int j=0;j<my_map->vexnum;j++){printf("%-4d",my_map->tyust[i][j]);}cout<<endl;}cout<<endl;
}
Graph  creat_graph()//创建有向图
{char in1,in2;int vexnum,arcnum;int p1,p2,weiget;Graph  pit=(Graph)malloc(sizeof(graph));cout<<"请输入顶点数和边数"<<endl;cin>>vexnum>>arcnum;pit->arcnum=arcnum;pit->vexnum=vexnum;for(int i=0;i<vexnum;i++){for(int j=0;j<vexnum;j++){pit->tyust[i][j]=INFINITY;}}cout<<"请输入顶点:"<<endl;for(int i=0;i<vexnum;i++)cin>>pit->vex[i];for(int i=0;i<arcnum;i++){cout<<"请输入边和权重"<<i+1<<endl;cin>>in1>>in2>>weiget;p1=get_pos(pit,in1);p2=get_pos(pit,in2);pit->tyust[p1][p2]=weiget;}print(pit);return pit;
}
void make_path(Graph g,bool *p,int k,int j)//路径寻找
{int start=k;//start等于开始点也就是0int MIN,MINNUM;while(start!=j){MIN=INFINITY;for(int k=0;k<g->vexnum;k++)//寻找最小的，这是符合我们的先前记录的顺序的{if(g->tyust[start][k]<MIN&&p[k]){MIN=g->tyust[start][k];MINNUM=k;}}if(MIN==INFINITY)break;printf("%c",g->vex[MINNUM]);if(MINNUM!=j)//不是终点printf("->");p[MINNUM]=false;//标志start=MINNUM;}cout<<endl;
}
int main()
{int k=0;Path p;short_table d;Graph g=creat_graph();bool *path=(bool *)malloc(g->vexnum*sizeof(bool));DIJ_shortestpath(g,k,p,d);cout<<"最短路径数组p[][]:n";for(int i=0;i<g->vexnum;i++){for(int j=0;j<g->vexnum;j++){cout<<p[i][j]<<" ";}cout<<endl;}cout<<endl;for(int i=0;i<g->vexnum;i++){if(i!=k&&d[i]<INFINITY)//如果不是起点，并且最终有路径到达{printf("%c->%c:%d  ",g->vex[k],g->vex[i],d[i]);printf("%c->",g->vex[k]);for(int j=0;j<g->vexnum;j++){path[j]=p[i][j];}make_path(g,path,k,i);//i是终点下标}}return 0;
}