最短路径(Dijkstra法)

2019-11-06 08:17:38

字体：大中小

来源：转载

供稿：网友

最短路径(Dijkstra法)

Dijkstra（迪杰斯特拉）算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

算法思想

按路径长度递增次序产生算法：把顶点集合V分成两组：（1）S：已求出的顶点的集合（初始时只含有源点V0）（2）V-S=T：尚未确定的顶点集合将T中顶点按递增的次序加入到S中，保证：（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的长度 T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

算法步骤

1. G={V,E}，初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值若不存在<V0,Vi>，d(V0,Vi)为∞ 2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中 3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值 4. 重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

算法实现

#include <iostream>#include <malloc.h>using namespace std;#define MAX_NUM 10000//MAX_NUM表示没有路径，即无穷大，如果设定为INT_MAX，会出现溢出情况，因此该值可根据情况改变#define VRType int#define VertexType int#define MAX_VERTEX_NUM 30typedef struct{ VertexType vex[MAX_VERTEX_NUM]; VRType edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum,arcnum;}MGraph;void CreatMGraph(MGraph &G, int n){ G.vexnum = n; for(int i = 0; i < G.vexnum; i++){ G.vex[i] = i; for(int j = 0; j < G.vexnum; j++){ cin>>G.edges[i][j]; if(!G.edges[i][j]) G.edges[i][j] = MAX_NUM; } }}void Dijkstra(MGraph G, VRType v, int distance[], int path[]){//diatance数组表示当前已找到的从v0到每个终点vi点的距离//path数组中保存从v0到vi最短路径上vi的前一个顶点//visit数组跟图的两种遍历中的一样，这里是判断是(1)否(0)找到从vo到vi的最短路径 int i, j, k, min; int visit[MAX_VERTEX_NUM] = {0}; k = v; visit[k] = 1; path[k] = -1; for(i = 0; i < G.vexnum; i++){ if(!visit[i]){ distance[i] = G.edges[k][i]; if(distance[i] < MAX_NUM) path[i] = k; } } for(i = 1; i < G.vexnum; i++){ min = MAX_NUM; for(j = 0; j < G.vexnum; j++) if((distance[j] < min) && (!visit[j])){ min = distance[j]; k = j; } visit[k] = 1; for(j = 0; j < G.vexnum; j++) if((!visit[j]) && ((distance[k] + G.edges[k][j]) < distance[j])){ //先判断是否找到该点的最短路径，如果没有，则判断从k点到i点的距离和是否小于distance[j] distance[j] = distance[k] + G.edges[k][j]; path[j] = k; } }}int main(){ int n; MGraph g; cin>>n; CreatMGraph(g, n); int distance[MAX_VERTEX_NUM] = {0}; int path[MAX_VERTEX_NUM]; Dijkstra(g, 0, distance, path); //假设从v = 0 cout<<" Vertex:"; for(int i = 0; i < g.vexnum; i++) cout<<g.vex[i]<<' '; cout<<endl; cout<<"Distance:"; for(i = 0; i < g.vexnum; i++) cout<<distance[i]<<' '; cout<<endl; return 0;}

上一篇：eclipse快捷键包括查找类、方法、变量

下一篇：typedef