求程序 在matlab上用Dijkstra和Floyd算法求出v1到v8的最短路径。。

Question

如题所述

Answer 1

function [ distance, path] = Dijkstra( W,st,e )  
    n=length(W);
    D = W(st,:);  
    visit= ones(1:n); 
    visit(st)=0;  
    parent = zeros(1,n); 
    path =[];  

    for i=1:n-1  
        temp = [];  
        for j=1:n  
           if visit(j)  
               temp =[temp D(j)];  
           else  
               temp =[temp inf];  
           end
        end
        [~,index] = min(temp);  
        visit(index) = 0;  

         for k=1:n  
            if D(k)>D(index)+W(index,k)  
               D(k) = D(index)+W(index,k);  
               parent(k) = index;  
            end  
        end 
    end  

    distance = D(e);
    t = e;  
    while t~=st && t>0  
        path =[t,path];  
        p=parent(t);t=p;  
    end  
    path =[st,path];%最短路径 
end

W = [0   3    10  Inf Inf Inf Inf Inf;
     3   0    Inf 5   Inf Inf Inf Inf;
     10  Inf  0   6   Inf Inf Inf Inf;
     Inf 5    6   0   4   Inf Inf Inf;
     Inf Inf Inf  4   0   9   5   Inf;
     Inf Inf Inf  Inf 9   0   3   4;
     Inf Inf Inf  10  5   3   0   6;
     Inf Inf Inf  Inf Inf 4   6   0    ];
 [distance,path]=Dijkstra(W,1,8);
 
 
 >> distance
distance =
    23
>> path
path =
     1     2     4     5     7     8

Answer 2

网上有代码。其实有自带函数，graphshortestpath和 graphallshortestpath。floyd算法求任意两点的距离本回答被网友采纳

Answer 3

你这个是数学建模吗追问

是啊

追答

可惜我是纯计算机专业的，数学并不好，不能帮你了

追问

我也是纯计算机专业，但是要学matlab，属于选修，谢了。我已经编完了。。