Matalab代码实现 Dijkstra求有向图及无向图之间，任意两点之间

<span style="font-family: Arial, Helvetica, sans-serif;">%% Dijkstra </span>function minWeightMatrix=shortestPath(G,nodeNum)minWeightMatrix=zeros(nodeNum,nodeNum);for i=1:nodeNum %获取每个顶点到其它节点最短路径权值，Dijkstra 源点遍历D=G(i,:); %初始化节点到各个邻居节点的权值D(D==0)=inf;tag=zeros(1,nodeNum); %0 为对应位置节点未求出最大路径tag(i)=1;while sum(tag,2)~=nodeNumnoTag=find(tag==0); %还未获得最短距离的节点minValue=min(D(noTag));if minValue~=inftempIndex=find(D==minValue); %找出候选节点，更新值tag(tempIndex)=1;% 将候选节点去掉for candidateNode=1:length(tempIndex)noTag(noTag==tempIndex(candidateNode))=[];end% 修改源点到各个未标记的顶点间的距离for j=1:length(noTag) %对所有未获得最短距离的节点进行更新minTemp=D(noTag(j));for k=1:length(tempIndex)if minTemp>(minValue+G(tempIndex(k),noTag(j)))&&G(tempIndex(k),noTag(j))~=0minTemp=minValue+G(tempIndex(k),noTag(j));endendD(noTag(j))=minTemp;endelsebreak;endendminWeightMatrix(i,:)=D;endminWeightMatrix(isinf(minWeightMatrix))=0;minWeightMatrix=minWeightMatrix-diag(diag(minWeightMatrix));

测试数据：

clear;clc;%% 测试数据%有向图范例G=[0 0 10 0 30 100;0 0 5 0 0 0;0 0 0 50 0 0;0 0 0 0 0 10;0 0 0 20 0 60;0 0 0 0 0 0];%% 无向图范例G=[0 0 10 0 30 100; 0 0 5 0 0 0; 10 5 0 50 0 0; 0 0 50 0 20 10; 30 0 0 20 0 60; 100 0 0 10 60 0];minPath=shortestPath(G,6);disp('测试完毕');

，才能做到人在旅途，感悟人生，享受人生。

相关文章：

你感兴趣的文章：

标签云：