最短路徑的教學反思

❶ 最短路徑中的修橋問題是怎麼作圖的

我估計這兩村在河兩岸不是直接對上的。你畫個圖，河的兩岸和兩個村莊各組成一個三角形，然後兩個斜邊和加上河寬就是兩村距離，然後用三角形定理來確定最小值就行了。說不說不清楚，你畫個圖好好研究吧。

❷ "最短路徑優先演算法"的優缺點

這個演算法一般出現在網路中，用於路由器的路由定址，我也只了解這方面內的優缺點。如果不對，容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，這便是最短路徑，前面的答案都是錯的，題主注意