-
让品牌有温度、有情感
专注品牌策划15年
如何求最短路径（如何求最短路径数据结构）
发布时间：2023-04-14 09:14:17
稿源：
创意岭 阅读：
50
大家好！今天让创意岭的小编来大家介绍下关于如何求最短路径的问题，以下是小编对此问题的归纳整理，让我们一起来看看吧。
开始之前先推荐一个非常厉害的Ai人工智能工具，一键生成原创文章、方案、文案、工作计划、工作报告、论文、代码、作文、做题和对话答疑等等
只需要输入关键词，就能返回你想要的内容，越精准，写出的就越详细，有微信小程序端、在线网页版、PC客户端
创意岭作为行业内优秀的企业，服务客户遍布全球各地，如需了解SEO相关业务请拨打电话175-8598-2043，或添加微信：1454722008
本文目录:
一、求A到B之间的最短路径，怎么获取
问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径。解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法，另外还有著名的启发式搜索算法A*，不过A*准备单独出一篇，其中Floyd算法可以求解任意两点间的最短路径的长度。任意一个最短路算法都是基于这样一个事实：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点到B。
(1) 迪杰斯特拉(Dijkstra)算法按路径长度(看下面表格的最后一行，就是next点)递增次序产生最短路径。先把V分成两组：
S：已求出最短路径的顶点的集合
V-S=T：尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到S中，依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值或是从V0经S中顶点到Vk的路径权值之和（反证法可证，说实话，真不明白哦）。
(2) 求最短路径步骤
初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值， 若存在<V0,Vi>，为<V0,Vi>弧上的权值（和SPFA初始化方式不同），若不存在<V0,Vi>，为Inf。
从T中选取一个其距离值为最小的顶点W(贪心体现在此处)，加入S(注意不是直接从S集合中选取，理解这个对于理解vis数组的作用至关重要)，对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值（上面两个并列for循环，使用最小点更新）。
重复上述步骤，直到S中包含所有顶点，即S=V为止（说明最外层是除起点外的遍历）。
二、最短路径求最值12个模型详解
最短路径求最值12个模型详解见下：
问题一：在直线 l 上求一点 P，使得 PA + PB 值最小 .
作法：连接 AB，与直线 l 的交点即为 P 点 .
原理：两点之间线段最短 . PA + PB 最小值为 AB .
问题二：（“将军饮马问题”）在直线 l 上求一点 P，使得 PA + PB 值最小 .
作法：作点 B 关于直线 l 的对称点 B＇，连接 AB' 与 l 的交点即为点 P．
原理：两点之间线段最短． PA + PB 最小值为 AB' .
问题三：在直线 l1、l2 上分别求点 M、N，使得 △PMN 的周长最小．
作法：分别作点 P 关于两条直线的对称点 P' 和 P''，连接 P'P''，与两条直线的交点即为点 M，N．
原理：两点之间线段最短． PM + MN + PN 的最小值为线段 P'P'' 的长．
问题四：在直线 l1、l2 上分别求点 M、N，使四边形 PQMN 的周长最小．
作法：分别作点 Q 、P 关于直线 l1、l2 的对称点 Q' 和 P' 连接 Q'P'，与两直线交点即为点 M，N.
原理：两点之间线段最短． 四边形 PQMN 周长的最小值为线段 Q'P' + PQ 的长．
问题五：（“造桥选址问题”）直线 m∥n，在 m、n 上分别求点 M、N，使 MN⊥m，
且 AM + MN + BN 的值最小．
作法：将点 A 向下平移 MN 的长度单位得 A'，连接 A'B，交 n 于点 N，过 N 作 NM⊥m 于 M .
原理：两点之间线段最短 . AM + MN + BN 的最小值为 A'B + MN .
问题六：在直线 l 上求两点 M , N （M 在左），使 MN = a , 并使 AM + MN + NB 的值最小 .
作法：将点 A 向右平移 a 个长度单位得 A'，作 A' 关于直线 l 的对称点 A''，连接 A''B 交直线 l 于点 N，
将 N 点向左平移 a 个单位得 M .
原理：两点之间线段最短 . AM + MN + NB 的最小值为 A''B + MN .
问题七：在 l1 上求点 A，在 l2 上求点 B，使 PA + AB 值最小 .
作法：作点 P 关于 l1 的对称点 P'，作 P'B⊥l2 于点 B，交 l1 于点 A .
原理：点到直线，垂线段的距离最短 . PA + AB 的最小值为线段 P'B 的长 .
问题八：A 为 l1上一定点，B 为 l2 上一定点，在 l2 上求点 M，在 l1上求点 N，
使 AM + MN + NB 的值最小 .
作法：作点 A 关于 l2 的对称点 A' , 点 B 关于 l1 的对称点 B'，连接 A'B' 交 l2 于点 M，交 l1 于点 N．
原理：两点之间线段最短． AM + MN + NB 的最小值为线段 A'B' 的长．
问题九：在直线 l 上求一点 P，使 | PA - PB | 的值最小．
作法：连接 AB，作 AB 的中垂线与直线 l 的交点即为 P 点．
原理：垂直平分上的点到线段两端点的距离相等． | PA - PB | = 0 .
问题十：在直线 l 上求一点 P，使 | PA - PB | 的值最大．
作法：作直线 AB，与直线 l 的交点即为 P 点．
原理：三角形任意两边之差小于第三边． | PA - PB | ≤ AB ， | PA - PB | 的最大值 = AB .
问题十一：在直线 l 上求一点 P，使 | PA - PB | 的值最大．
作法：作点 B 关于直线 l 的对称点 B' 作直线 AB'，与直线 l 的交点即为 P 点．
原理：三角形任意两边之差小于第三边． | PA - PB | ≤ AB' ， | PA - PB | 的最大值 = AB' .
问题十二：（“费马点”）△ABC 中每一内角都小于 120°，在 △ABC 内求一点 P，
使得 PA + PB + PC 的值最小 .
作法：所求点为 “费马点” ，即满足 ∠APB = ∠BPC = ∠APC = 120° .
以 AB 、 AC 为边向外作等边 △ABD、△ACE，连接 CD、BE 相交于点 P，点 P 即为所求 .
原理：两点之间线段最短 . PA + PB + PC 的最小值 = CD .
三、数据结构求最短路径
用Dijkstra算法求从V1顶点到其他各顶点的最短距离和最短路径的C语言程序如下
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 6 // 顶点数
#define INF 32767
int adj_arr[N][N] = {{INF, 2, 3, INF, INF, INF},
{INF, INF, INF, 5, INF, INF},
{INF, INF, INF, 3, 10, INF},
{INF, INF, INF, INF, INF, 4},
{INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, 2, INF}}; // 用一个全局二维数组存储带权有向图的邻接矩阵
void shortest_path(int start, int end);
void print_shortest_path(int* distance,int* path,int* used,int start,int end);
int main(){
int i;
char s1[3];
for(i=1;i<6;i++){
shortest_path(0, i);
}
return 0;
}
void shortest_path(int start, int end){ // 基于Dijkstra算法的最短路径函数
int distance[N]; // 用于存放起始点到其余各点的最短距离
int path[N]; // 用于存放起始点到其余各点最短路径的前一个顶点
int used[N] = { 0 }; // 用于标记该顶点是否已经找到最短路径
int i, j, min_node, min_dis, pass_flag = 0;
for(i = 0; i < N; i++){
distance[i] = adj_arr[start][i]; // 初始化距离数组
if(adj_arr[start][i] < INF){
path[i] = start; // 初始化路径数组
}else{
path[i] = -1;
}
}
used[start] = 1;
path[start] = start;
for(i = 0; i < N; i++){
min_dis = INF;
for(j = 0; j < N; j++){
if(used[j] == 0 && distance[j] < min_dis){
min_node = j;
min_dis = distance[j];
pass_flag++; // 标记是否存在通路
}
}
if(pass_flag != 0){
used[min_node] = 1;
for(j = 0; j < N; j++){
if(used[j] == 0){
if(adj_arr[min_node][j] < INF && distance[min_node] + adj_arr[min_node][j] < distance[j]){
distance[j] = distance[min_node] + adj_arr[min_node][j];
path[j] = min_node;
}
}
}
}else{
printf("没有通路!n");
return;
}
}
print_shortest_path(distance, path, used, start, end);
return;
}
void print_shortest_path(int* distance,int* path,int* used,int start,int end){ // 输出最短距离并打印最短路径
int i = 0, pre, inverse_path[N];
char s1[3],s2[3];
sprintf(s1, "V%d", (start+1));
sprintf(s2, "V%d", (end+1));
printf("从%s顶点到%s顶点的最短距离: %dn", s1, s2, distance[end]);
inverse_path[i] = end;
pre = path[end];
if(pre == -1){
printf("没有通路!n");
}else{
while(pre != start){
inverse_path[++i] = pre;
pre = path[pre];
}
inverse_path[++i] = start;
printf("从%s顶点到%s顶点的最短路径:n", s1, s2);
for(; i > 0; i--){
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s -> ", s1);
}
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%sn", s1);
}
return;
}
四、求出最短路径，要过程，用Dijkstra算法。。。
从v1开始遍历
v2 = 2;
v3 = 5;
v2较小所以跳到v2
v3 = 4;
v4 = 6;
v5 = 8;
v3较小所以跳到v3
v4 = 5;
v6 = 7;
v4较小所以跳到v4
v6 = 6;
v7 = 9;
v6较小所以跳到v6
v7 = 8;
所以最后结果v1 -> v7最短路径为v1->v2->v3->v4->v6->v7,最短路径长度为8
以上就是关于如何求最短路径相关问题的回答。希望能帮到你，如有更多相关问题，您也可以联系我们的客服进行咨询，客服也会为您讲解更多精彩的知识和内容。
推荐阅读：
赣公网安备 50019002502384号
