最短路径的教学反思

❶ 最短路径中的修桥问题是怎么作图的

我估计这两村在河两岸不是直接对上的。你画个图，河的两岸和两个村庄各组成一个三角形，然后两个斜边和加上河宽就是两村距离，然后用三角形定理来确定最小值就行了。说不说不清楚，你画个图好好研究吧。

❷ "最短路径优先算法"的优缺点

这个算法一般出现在网络中，用于路由器的路由寻址，我也只了解这方面内的优缺点。如果不对，容LZ就别看了。
所谓最短路径，实际上说的是跳数。比如从一条路走会经过三个路由器，而从另一条路走，会经过两个路由器，那么此算法会判断2跳比3跳要短，但具体每一跳会花多长时间，经过多长路程，它不会考虑的。所以不一定算法的最短路径就是真实的最短。因为很多因素算法没有考虑，比如通信质量，网线长度……
C语言我只看过一个模拟现实的例子，大概是说公车走什么路线长度最短，那个算法考虑的是路线的长短，而不是跳数，优点当然就是路线的绝对最短，缺点就是没考虑到其他现实因素，比如是否堵车（相当于网络通信质量）之类。
总之不管什么算法，考虑到的因素就是它的优点，反过来说，缺点往往就是算法忽略的因素。
补充一下，如果说的不是算法本身的优劣，而是细节的实现方面，那就是从时间复杂度和空间复杂度两个方面去考虑了，希望对LZ有用。

❸ 数据结构课程设计最短路径的求解 这是程序，出现错误了，不知道怎么改

数据结构课程设计 怎么做]de

❹ 最短路径算法在现实生活中具有哪些实际的应用

供暖、供气、供电、供水管道等的的费用节省问题
公路修建的费用节省问题

❺ 关于最短路径的优化问题编程matlab

以前搞建模在网上下到的代码，不是自己编的，但经过试验可以用，分享了：

function len=dijkstra(Input)
%最短路Dijkstra算法,同时给出路径，input为图矩阵

row=size(Input,1);

%赋初值
% s_path=1;
distance=inf*ones(1,row);
distance(1)=0;
% flag(1)=1;
temp=1;

%求起点到各点的最短路的权
% s_path=ones(1,3);
while length(s_path)<row
pos=find(Input(temp, : )~=inf);
n=length(pos);
flag=ones(1,n);
for i=1:n
if (isempty(find(s_path==pos(i),1)))&&(distance(pos(i))>...
(distance(temp)+Input(temp,pos(i))))
distance(pos(i))=distance(temp)+Input(temp,pos(i));
flag(pos(i))=temp;
end
end
k=inf;
for i=1:row
if (isempty(find(s_path==i,1)))&&(k>distance(i))
k=distance(i);
temp_2=i;
end
end
s_path=[s_path,temp_2];
temp=temp_2;
end

%用追溯法得到起点到各点的最短路的路线
len=zeros(1,row);
for endpoint=1:row
path=0; %初始化
path(1)=endpoint;
i=1;
while path(i)~=1
path(i+1)=flag(path(i));
i=i+1;
end
path(i)=1;
path=path(end:-1:1); %最短路径
short_distance=distance(endpoint); %最短路径权
len(endpoint)=short_distance; %起点到各点的最短距离
pathall{endpoint}=path; %总路径矩阵
end

len=len(25:end);

%{
disp('起点到各点的最短路径：');
celldisp(pathall);
%设法只画出最短路径
em=find(w==inf);
w(em)=0;
h = view(biograph(w,[],'ShowWeights','on'));
%}
邮箱给你发了个资料，多年前搞的，估计是忘了，也许这个函数有点问题，你按资料里的做吧

❻ 想要求一篇关于最短路径研究的一段英文文献（附中文翻译）

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算回法。是从一个顶点到其余答各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra algorithm is made by Holland computer scientist Dijkstra in 1959, so it is called Stella Dick algorithm. The shortest path algorithm from one vertex to the rest of the vertices is the shortest path problem in the directed graph.. Dijkstra algorithm is characterized by the starting point as the center of the expansion of the center, until the end of the extension.

❼ 关于时间依赖的最短路径算法

Dijkstra 最短路径算法的一种高效率实现*

随着计算机的普及以及地理信息科学的发展，GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用，而网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等（如110报警、119火警以及医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间应该在1 s～3 s内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。其实,无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法。
据统计，目前提出的此类最短路径的算法大约有17种。F.Benjamin Zhan等人对其中的15种进行了测试，结果显示有3种效果比较好，它们分别是：TQQ（graph growth with two queues）、DKA (the Dijkstra's algorithm implemented with approximate buckets) 以及 DKD (the Dijkstra

❽ 求助python的最短路径问题

这是一个深度优先搜索算法（Deepth First Search, DFS）

算法核心是不断递归，直到找到目标，入队一种可能方案，return返回上一递归，再次尝试以当前点开始计算有没有其他方案，如有则继续递归并入队，如没有则再次return

简单来说就是这样的结构：

def dfs(position, value):

# position 传参位置，value 传参到现在的计算结果

if 到达目标:

判断value是否比最短路径短

return value

else:

for x in position的所有可能下一路径:

if x在路径列表中:

# 不能有重复路径，变成回环

continue

else:

获取路径x的值

改变position

入队 dfs(new_position, value+x

这个代码用的是字典存储每个点可到达的点以及路程

然后深度优先搜索

不懂再追问

❾ 最短路径问题会的大神说下谢谢如图

我看其他回答好抄像都是错的，我给你正袭确答案，分别以小草和小河为对称轴，做A的对称点，将得到的两个点相连，与小草和小河分别有两个交点B与C，连接ABBCCA，这便是最短路径，前面的答案都是错的，题主注意