dijkstra1.m

利用MATLAB来实现Dijkstra算法模拟了路由选择协议

% Lab 02
% WiCom_1
% By Kashif Shahzad 
% 01-ET-31
% 3rd June 2004
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% University of Engineering and Technology Taxila
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Design simulation and implementation of Dijkstra's shortest
% path algorithm by Kashif Shahzad
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Program Description + Sample Output
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Lets say that there are 3 nodes A, B and C such that A is 
% connected to both B and C but B and C are not connected
% So lets say that weight on the link between the node A and B is
% 2 and the weight between A and C is 5, B and C are of course not 
% connected so there is infinite weight between them, When u run 
% the program for this u will have to put your first input as
%
% "Please enter the number of nodes less than 26 = 3"
%
% Then inputs in command prompt for this case will be
%
% Enter Weight between [A][A] = 0
% Enter Weight between [A][B] = 2
% Enter Weight between [A][C] = 5
% Enter Weight between [B][A] = 2
% Enter Weight between [B][B] = 0
% Enter Weight between [B][C] = inf
% Enter Weight between [C][A] = 5
% Enter Weight between [C][B] = inf
% Enter Weight between [C][C] = 0

% Yes it is important to know that communication cost between A and A is
% zero and where there is no link cost is INF (Matlab Key word for infinity)
% Lets say u wanna start from B and wanna reach C so u enete as follows
%
% Please enter the source node = 2
% Please enter the destination node = 3
%
% The answer would be BAC with weight 7
% remember this program takes weight greedily, lets say u wanna communicate
% between A and B and A is connected to both B and C, also B and C are
% connected, if weight between A and B is 5 and between A and C is 1 and
% even later on cost between B and C is 10 still A would chose to go to C
% through B because when on node A as source it will decide that cost
% between A and C is less that cost between A and B
clc
clear

msgbox('This programme is written by Kashif Shahzad 01-ET-31','Hay Beware !!!','warn');
pause(3);
msgbox('You are requested to move to command prompt','Kashif Tips','help');

% Taking number of input nodes from user
n=input('Please enter the number of nodes less than 26 = ');

% Checking for bad input
if n > 26
    error('Plzz follow the instructions by Kashif')
end

% Defining node numbers interms of Alphabets
alphabets= char(65:1:65+n);

adj=zeros(n,n);
for p=1:n
    for q=1:n
        adj(p,q)=input(['Enter Weight between [',alphabets(p),']','[',alphabets(q),'] = ']);
    end
end

%Coversting status of all nodes to Tentative
for p=1:n
    a(p).status=0;
end

temp=[];
acc=[];

% Taking input from user regarding source & destination nodes

s=input('Please enter the source node = ');
t=input('Please enter the destination node = ');

% converting source node to status PERMANANT
a(s).status=1; 
path=s;

% if (adj(s,t)==0)
%     disp('Source and Destination are Same');
%     continue
% end


% Main algorithm of Greedy Dijkstra
for k=1:inf
for h=1:n
 if a(h).status==0   % If Unknown 
     temp=[temp adj(s,h)];
 else
     temp=[temp inf];
 end
end
[aa,bb]=min(temp);
acc=[acc aa];
temp=[];
s=bb;
a(s).status=1;
path=[path s];
if s==t
    break
end
end

% Creating dialogue box for Output
helpdlg(['Path : ' alphabets(path) '  Total Cost/Weight : '...
        num2str(sum(acc))],'Greedy Dijkstra Algorithm')