11-matlba-bellman-ford；地杰斯特拉

求最短路：

1.bellman-ford:

%求s到各点的最短距离

function Dist = Bellman_Ford(s)

    load cityJuli;

    for i = 1:154

        Dist(i) = inf;

    end

    Dist(s) = 0;

    flag = 1;

    for j = 1:154   %154个城市

        flag = 1;

        for i = 1 : 248 %题目给248组数据,遍历每一条边                      %用所给数据松弛

            if Dist(cityJuli(i,1)) > Dist(cityJuli(i,2)) + cityJuli(i,3)  %如果这条边的终点的dist[]值小于起始点的dist[]值加上这条边的权值，则更新dist

                Dist(cityJuli(i,1)) = Dist(cityJuli(i,2)) + cityJuli(i,3);

                flag = 0;

            end

            if Dist(cityJuli(i,2)) > Dist(cityJuli(i,1)) + cityJuli(i,3)  %由于是无向图，故要反向松弛一遍

                Dist(cityJuli(i,2)) = Dist(cityJuli(i,1)) + cityJuli(i,3);

                flag = 0;

            end

        end

        if(flag == 1)

            break;

        end

    end

end

%{

void bellman(int s){

    memset(d, MAX, sizeof(d));

    d[s] = 0; //必须初始化这个

    int flag = 1;

    for(int k = 0; k < n - 1; k++){

        flag = 1;

        for(int i = 0; i < m; i++){      //遍历每一条边

            if(d[u[i]] > d[v[i]] + w[i]){//如果这条边的终点的d[]值小于起始点的d[]值加上这条边的权值，则更新d

                d[u[i]] = d[v[i]] + w[i];

                flag = 0;

            }

        }

        if(flag){

            break;

        }

    }

}

%}

　　

2.地杰斯特拉：

function [ distance, path] = Dijk( W,st,e )

% W  权值矩阵   st 搜索的起点   e 搜索的终点

n=length(W);%节点数

D = W(st,:);

for i = 1:n

    visit(i) = 1;

end

visit(st)=0;

parent = zeros(1,n);%记录每个节点的上一个节点

path =[];

for i=1:n-1

    temp = [];

    %从起点出发，找最短距离的下一个点，每次不会重复原来的轨迹，设置visit判断节点是否访问

    for j=1:n

       if visit(j)

           temp =[temp D(j)];

       else

           temp =[temp inf];

       end

    end

    [value,index] = min(temp);

    visit(index) = 0;

    %更新 如果经过index节点，从起点到每个节点的路径长度更小，则更新，记录前趋节点，方便后面回溯循迹

    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