打字猴:1.70101005e+09
1701010050
1701010051
1701010052
1701010053
1701010054 (3)修正,则有公式:
1701010055
1701010056
1701010057
1701010058
1701010059 继续转(2),即按照下面的循环计算。
1701010060
1701010061
1701010062 (4),则有:
1701010063
1701010064
1701010065
1701010066
1701010067
1701010068 (5)修正,则有公式:
1701010069
1701010070
1701010071
1701010072
1701010073 编写dijkstra()函数如下:
1701010074
1701010075     function [r_path, r_cost] = dijkstra(pathS, pathE, transmat)    %  pathS: 所求最短路径的起点    %  pathE: 所求最短路径的终点    %  transmat: 图的转移矩阵或者邻接矩阵,应为方阵    if ( size(transmat,1) ~= size(transmat,2) )      error( ‘detect_cycles:Dijkstra_SC’, …             ‘transmat has different width and heights’ );    end    %初始化:    % noOfNode-图中的顶点数    % parent(i)-节点i的父节点    % distance(i)-从起点pathS的最短路径的长度    % queue-图的广度遍历    noOfNode = size(transmat, 1);    for i = 1:noOfNode      parent(i) = 0;      distance(i) = Inf;    end    queue = [];        %从pathS: 所求最短路径的起点开始寻找最短路径    for i=1:noOfNode      if transmat(pathS, i)~=Inf         distance(i) = transmat(pathS, i);        parent(i)   = pathS;        queue       = [queue i];      end    end        %对图进行广度遍历    while length(queue) ~= 0      hopS  = queue(1);      queue = queue(2:end);            for hopE = 1:noOfNode        if distance(hopE) < distance(hopS) + transmat(hopS,hopE)          distance(hopE) = distance(hopS) + transmat(hopS,hopE);          parent(hopE)   = hopS;          queue          = [queue hopE];        end      end          end        %回溯进行最短路径的查找    r_path = [pathE];        i = parent(pathE);        while i~=pathS && i~=0      r_path = [i r_path];      i      = parent(i);    end    if i==pathS      r_path = [i r_path];    else      r_path = []    end    %返回最短路径的权和    r_cost = distance(pathE);
1701010076
1701010077 主程序如下:
1701010078
1701010079     clc                   %清屏    clear all;            %删除workplace变量    close all;            %关掉显示图形窗口    warning off           %消除警告    W=[0 1 2 Inf 7 4 8 Inf ;       1 0 2 5 Inf Inf 7 Inf ;       2 2 0 1 5 Inf Inf Inf;       Inf 5 1 0 3 Inf Inf 6 ;       7 Inf 5 3 0 3 Inf 4 ;       4 Inf Inf Inf 3 0 2 6;       8 7 Inf Inf Inf 2 0 4;       Inf Inf Inf 6 4 6 4 0];    [r_path, r_cost] = dijkstra(1, 8, W)
1701010080
1701010081 运行程序输出结果如下:
1701010082
1701010083     r_path =         1     3     4     8    r_cost =         9
1701010084
1701010085 整理结果如下:
1701010086
1701010087
1701010088
1701010089
1701010090 有结果可知从城市v1到城市v8的最短距离为9,中间需要经过城市v3和城市v4。具体如图8-23所示。
1701010091
1701010092
1701010093
1701010094
1701010095
1701010096 图8-23 最短路径图
1701010097
1701010098 最小树模型和最短路模型有区别,最短路问题强调用户从起点到终点的最短路程,即所耗费的资源最小,而最小树模型是链接所有节点,构成的网络的权值是最小的。最短路模型在现实中应用广泛,特别是对于物流运输业而言,当然是路程越短越好,节约时间和成本,一直是企业追求的目标,然而最短路模型能够为用户提供技术支持。
1701010099
[ 上一页 ]  [ :1.70101005e+09 ]  [ 下一页 ]