1. 适用范围:
- 对非负权值网中
- 求某两个顶点的最短路径
- 求某个顶点到其他全部顶点的最短路径
2. 算法思想:
- use::动态规划
2.1. 直观理解:
2.1.1. 梗概: 步步为营, 一边探图, 一边逐个确定所有顶点的最短路径
2.1.2. 要点:
- 对每个顶点, 都通过不断刷新最短路径, 来选出最短路径
算法设计过程
画一颗解空间树 发现最短路径中任意两个顶点之间的距离也是最短的, 满足最优子结构 所以可以采用分治法将问题拆分为源顶点到中点+中点到终点 在某一个最短顶点中选择最短的相邻顶点A, 则A的最短路径已经确定了 未完待续… 到达不了的顶点也可以抽象成距离无限大的路径, 这样方便搜索
3. 在c语言中的实现
3.1. 算法动画:
【算法】最短路径查找—Dijkstra算法_哔哩哔哩_bilibili
3.2. 梗概:
3.2.1. 需要一个表, 每个结点代表一个顶点, 每个结点分三部分存储
3.2.1.1. 最短顶点标记
表示出发点到该顶点的最短路径已确定
3.2.1.2. 临时最短路径长度
表示暂时的最短路径长度(出发点到该顶点)
3.2.1.3. 回头顶点
- 存储暂时最短路径路径的上一个顶点
- 用来原路返回
3.2.2. 初始化所有顶点的临时最短路径长度为无穷大, 表示不可达
3.2.3. 初始化起点的邻接点的临时最短路径长度, 为起点到该邻接点的长度
3.2.4. 重复贪心探图, 直到所有顶点都标记为最短顶点
3.2.4.1. 先从所有顶点中选择临时最短路径长度最短的, 将其标记为最短顶点
3.2.4.2. 对新最短顶点的所有邻接点, 更新其最短路径数据
如果从起点⇒新最短顶点⇒该邻接点, 其长度比该邻接点记录的最短长度还要短, 则更新之 否则不更新
3.2.5. 得到结果
- 确定了起点到所有顶点的最短路径与长度, 从中按需筛选出目标顶点
- 一路沿着目标顶点的回头顶点, 直到起点, 就是逆最短路径
3.3. 代码:
int ShortestPath_DJS(AdjMatrix *G,int start,int end,int Shortestpath[]){
/*dis[i]为起点到顶点i的最短距离*/
int dis[MAX_VERTEX_NUM];
/*visit[i]=1用来标记顶点i为最短顶点*/
int visit[MAX_VERTEX_NUM];
/*prevetrix[i]表示顶点i的回头顶点位置*/
int prevetrix[MAX_VERTEX_NUM];
int count = 0;//count是已求出最短顶点总数
visit[start] = 1;
prevetrix[start] = start;
count++;
for (int i=1;i<G->vexnum;i++){//初始化
dis[i]=INFINITY;
prevetrix[i] = start;
}
/*循环直到所有顶点都找到最短路径*/
for(;count<G->vexnum;){
int min = INFINITY, target_index;
for (int i = 1; i < G->vexnum; i++){
if (visit[i] == 0 && min > dis[i]){
min = dis[i];
target_index = i;
}
}//找路径最短的未探索顶点
visit[target_index] = 1;
count++;
/*更新当前顶点的邻接点*/
for (int i = 1; i < G->vexnum; i++)
{
if (visit[i] == 0 && dis[target_index] +
G->arcs[target_index][i].adj < dis[i]){
dis[i]=dis[target_index]+G->arcs[target_index][i].adj;
prevetrix[i] = target_index;
}
}
}
return dis[end];
int j=1,i;
Shortestpath[0]=end;
/*沿着prevetrix[目标顶点]一路往回,即最短路径的反向*/
for(i=prevetrix[end];prevetrix[i]!=start;i=prevetrix[i],++j)
Shortestpath[j]=i;
for(;i<j;++i,--j){
int temp;
temp=Shortestpath[i];
Shortestpath[i]=Shortestpath[j];
Shortestpath[j]=temp;
}
}4. 手动运算
列一个表, 行为从小到大的每个顶点 列分别为最短顶点标记, 与目前最短路径长度
- 按算法步骤一次次选出最短顶点, 标记的时候用序号标记
- 更新目前最短路径长度 的时候, 不用划掉, 直接在后面追加
- 不用记录前驱顶点, 等到全部顶点都确定完之后, 根据直觉确定每个顶点的路径