首页 > 代码库 > Dijkstra算法（邻接矩阵存储）
Dijkstra算法（邻接矩阵存储）
首先我们需要熟悉Dijkstra算法的原理：
从某个源点到其余各顶点的最短路径，即单源点最短路径。单源点最短路径是指：给定带权有向图G和源点v，求从v到G中其余各顶点的最短路径。迪杰斯特拉（Dijkstra）提出了按路径长度递增的顺序产生各顶点的最短路径算法。
该算法的基本思想是：
（1）设置两个顶点的集合S和T＝V－S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点；
（2）初始状态时，集合S中只包含源点v0；
（3）从集合T中选取到某个顶点vi（要求vi到v0的路径长度最小）加入到S中；
（4）S中每加入一个顶点vi，都要修改顶点v0到T中剩余顶点的最短路径长度值，它们的值为原来值与新值的较小者，新值是vi的最短路径长度加上vi到该顶点的路径长度；
（5）不断重复（3）和（4），直到S包含全部顶点。
算法的代码实现很巧妙：
1.首先函数里面运用数组D[n]表示源点到节点n的最短距离，s[n]表示某一节点n是否已经进入集合S，如果进入则将s[i]置为1.P[n]表示当前节点n的前驱节点（用来输出路径）。
2.在开始遍历之前，首先给数组D[n]赋值为源点到该点的距离，这样便能第一次找到源点到相邻节点的最短距离（D[i]=C[v1][i];）。
3.下面找出最短距离：
if((!S[j])&&(D[j]<min))
{
min=D[j];
k=j;
}
4.更新各节点的最短距离：
for(j=0;j<n;j++)
{
if((!S[j])&&(D[j]>D[k]+C[k][j]))//调整各节点（未进入集合S）的距离值
{
D[j]=D[k]+C[k][j]; //修改蓝点j+1的距离
P[j]=k+1; //k+1是j+1的前趋
}
}
4.代码实现：
1 #include<stdio.h> 2 #define maxsize 1000 //表示两点间不可达，距离为无穷远 3 #define n 7 //结点的数目 4 void dijkstra(int C[][n],int v);//求原点v到其余顶点的最短路径及其长度 5 void main() 6 { 7 8 //对邻接矩阵进行赋值，没有直接连通的赋值为maxsize 9 int C[n][n]= 10 { 11 {maxsize,13,8,maxsize,30,maxsize,32}, 12 {maxsize,maxsize,maxsize,maxsize,maxsize,9,7}, 13 {maxsize,maxsize,maxsize,5,maxsize,maxsize,maxsize}, 14 {maxsize,maxsize,maxsize,maxsize,6,maxsize,maxsize}, 15 {maxsize,maxsize,maxsize,maxsize,maxsize,2,maxsize}, 16 {maxsize,maxsize,maxsize,maxsize,maxsize,maxsize,17}, 17 {maxsize,maxsize,maxsize,maxsize,maxsize,maxsize,maxsize} 18 },v=1,i,j; 19 20 dijkstra(C,v);//迪杰斯特拉算法 21 22 } 23 void dijkstra(int C[][n],int v)//求原点v到其余顶点的最短路径及其长度 24 { 25 26 27 int D[n];//用来存储从起点到某一节点的最短距离 28 int P[n],S[n];//p[n]表示某一节点的父亲，s[n]相当于标志数组 29 int i,j,k,v1,pre; 30 int min,max=maxsize,inf=1200; 31 v1=v-1;//节点号和存储的数目差1 32 33 34 35 for(i=0;i<n;i++) 36 { 37 D[i]=C[v1][i]; //置初始距离值 38 if(D[i]!=max) //说明存在边 39 P[i]=v;//把父亲置为v 40 else 41 P[i]=0;//否则父亲置为0 42 } 43 44 45 46 for(i=0;i<n;i++) 47 S[i]=0; //如果某点i被访问则把该点值置为1，否则为0 48 49 50 51 S[v1]=1;//已经被访问置为1 52 D[v1]=0; //源点v送S 53 54 55 56 for(i=0;i<n-1;i++) //扩充红点集 57 { 58 59 60 min=inf;//令inf>max，保证距离值为max的蓝点能扩充到S中 61 for(j=0;j<n;j++)//在当前蓝点中选距离值最小的点k+1 62 { 63 if((!S[j])&&(D[j]<min)) 64 { 65 min=D[j];//找从起点开始的最小权值 66 k=j; 67 } 68 } 69 70 71 S[k]=1; //已经被访问，置为1 72 73 74 for(j=0;j<n;j++) 75 { 76 if((!S[j])&&(D[j]>D[k]+C[k][j]))//调整各蓝点的距离值 77 { 78 D[j]=D[k]+C[k][j]; //修改蓝点j+1的距离 79 P[j]=k+1; //k+1是j+1的前趋 80 } 81 } 82 83 84 } //所有顶点均已扩充到S中 85 86 87 for(i=0;i<n;i++)//输出结果和最短路径 88 { 89 printf("%d到%d的最短距离为",v,i+1); 90 printf("%d\n",D[i]); //打印结果 91 pre=P[i]; 92 printf("路径：%d",i+1); 93 while(pre!=0) //继续找前趋顶点 94 { 95 printf("<——%d",pre); 96 pre=P[pre-1]; 97 } 98 printf("\n"); 99 }100 101 102 }