算法描述
|描述:
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。由for循环可知,其时间复杂度是O(n^2)。
|原理:
在已知图的邻接矩阵 net.vexs[i ] [j](无向网,含权值的图)的条件下,通过遍历已知图的所有路径,用 dis[i] 数组来记录到i点的最短路径,然后在循环中不断判断更替。首先,将所有点的集合分为俩部分,一边是已经遍历过的,另外一边是没有遍历过的,分别用mark[i]=1、mark[i]=0来表示。层层扩散,实时比较和更新最短路径
|代码通解:
在下面代码中,先将赋予初始值dis[i]=INF(无穷大)、mark[i]=0(未标记),而后单独将源点(x)所联通的路径权值 net.arcs[x] [i]赋予dis[i](<INF称为初始化),i为联通的点,暂定为到i的最短路径,标记mark[x]=1,即已经遍历;然后,在一个for遍历了所有节点的大循环里面:①寻找遍历到点联通路径(与之相连线的点)中权值最小的一条; 标记遍历点; ②修正最短路径;
所有点遍历完成后,dis[i]也在不断的修正中得到真正的最小值,即最短路径。
算法实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
| #include<bits/stdc++.h>
#define INF 100 #define maxSize 7 #define number 12 using namespace std; typedef struct { int edges[maxSize][maxSize]; int n, e; }MGraph;
#define MAXSIZE 20 #define PLACENUM 12 #define INF 9999 struct { int vexnum,arcnum; int vexs[MAXSIZE]; int arcs[MAXSIZE][MAXSIZE]; } net;
void Dijkstra(int x,int y) { int i,j,k; int min; int u; int dis[net.vexnum]; int mark[net.vexnum]; for(i=0; i<net.vexnum; i++) { mark[i] = 0; dis[i] = net.arcs[x][i]; } mark[x]=1; for(k=0; k<net.vexnum; k++) { min = INF; for(i=0; i<net.vexnum; i++) { if(mark[i]==0&&min>dis[i]) { min = dis[i]; u=i; } } mark[u]=1; for(i=0;i<net.vexnum;i++) { if(!mark[i]&&dis[i]>dis[u]+net.arcs[u][i]) { dis[i] = dis[u] + net.arcs[u][i]; } } } printf("最短路径值为: %d",dis[y]); }
|