CommentCaMarche
Recherche
Posez votre question Signaler

Dijkstra [Fermé]

jeremie.lemoine 6Messages postés mercredi 1 décembre 2004Date d'inscription 3 janvier 2005Dernière intervention - Dernière réponse le 14 déc. 2010 à 23:52
Bonjour,

Je recherche l'algorithme de dijkstra en Matalab pour trouver le plus court chemin dans une matrice du point (i,j) au point (k,l).

Merci d'avance
Lire la suite 
Réponse
+3
moins plus
Voila une version de l'algo de dijkstra.
elle marche parfaitement!
Je crois qu avec ta méthode tu t'égares un peu...
Keep It Simple Stupid!
Ce fichier est naturellement copyrighté, donc si tu veux l'utiliser
pour qquechose de public ou privé tu dois raquer!

tchaou!

function D = dijk(A,s,t)
% dijk - shortest paths from nodes 's' to nodes 't' using Dijkstra algorithm.
%
%   D = dijk(A,s,t);
%
%     A = n x n node-node weighted adjacency matrix of arc lengths
%         (Note: A(i,j) = 0   => Arc (i,j) does not exist;
%                A(i,j) = NaN => Arc (i,j) exists with 0 weight)
%     s = FROM node indices
%       = [] (default), paths from all nodes
%     t = TO node indices
%       = [] (default), paths to all nodes
%     D = |s| x |t| matrix of shortest path distances from 's' to 't'
%       = [D(i,j)], where D(i,j) = distance from node 'i' to node 'j' 
%
%	(If A is a triangular matrix, then computationally intensive node
%   selection step not needed since graph is acyclic (triangularity is a 
%   sufficient, but not a necessary, condition for a graph to be acyclic)
%   and A can have non-negative elements)
%
%	(If |s| >> |t|, then DIJK is faster if DIJK(A',t,s) used, where D is now
%   transposed and P now represents successor indices)
%
%  (Based on Fig. 4.6 in Ahuja, Magnanti, and Orlin, Network Flows,
%   Prentice-Hall, 1993, p. 109.)

% Copyright (c) 1998-2000 by Michael G. Kay
% Matlog Version 1.3 29-Aug-2000
% 
%  Modified by JBT, Dec 2000, to delete paths
% Modified by AFELT 2004


% Input Error Checking ******************************************************
error(nargchk(1,3,nargin));

[n,cA] = size(A);

if nargin < 2 | isempty(s), s = (1:n)'; else s = s(:); end
if nargin < 3 | isempty(t), t = (1:n)'; else t = t(:); end

if ~any(any(tril(A) ~= 0))			% A is upper triangular
   isAcyclic = 1;
elseif ~any(any(triu(A) ~= 0))	% A is lower triangular
   isAcyclic = 2;
else										% Graph may not be acyclic
   isAcyclic = 0;
end

if n ~= cA
   error('A must be a square matrix');
elseif ~isAcyclic & any(any(A < 0))
   error('A must be non-negative');
elseif any(s < 1 | s > n)
   error(['''s'' must be an integer between 1 and ',num2str(n)]);
elseif any(t < 1 | t > n)
   error(['''t'' must be an integer between 1 and ',num2str(n)]);
end
% End (Input Error Checking) ************************************************

A = A';		% Use transpose to speed-up FIND for sparse A

D = zeros(length(s),length(t));
P = zeros(length(s),n);

for i = 1:length(s)
   j = s(i);
   
   Di = Inf*ones(n,1); Di(j) = 0;
   
   isLab = logical(zeros(length(t),1));
   if isAcyclic ==  1
      nLab = j - 1;
   elseif isAcyclic == 2
      nLab = n - j;
   else
      nLab = 0;
      UnLab = 1:n;
      isUnLab = logical(ones(n,1));
   end
   
   while nLab < n & ~all(isLab)
      if isAcyclic
         Dj = Di(j);
      else	% Node selection
         [Dj,jj] = min(Di(isUnLab));
         j = UnLab(jj);
         UnLab(jj) = [];
         isUnLab(j) = 0;
      end
      
      nLab = nLab + 1;
      if length(t) < n, isLab = isLab | (j == t); end
      
      [jA,kA,Aj] = find(A(:,j));
      Aj(isnan(Aj)) = 0;
            
      if isempty(Aj), Dk = Inf; else Dk = Dj + Aj; end
      
      P(i,jA(Dk < Di(jA))) = j;
      Di(jA) = min(Di(jA),Dk);
      
      if isAcyclic == 1			% Increment node index for upper triangular A
         j = j + 1;
      elseif isAcyclic == 2	% Decrement node index for lower triangular A
         j = j - 1;
      end
      
      %disp( num2str( nLab ));
   end
   D(i,:) = Di(t)';
end

Réponse
+1
moins plus
Merci quand même mais à chercher algo-info ou algoinfo ou .... je risque d'y passer beaucoup de temps

matlab- 3 janv. 2005 à 09:36
oui mais même les feignants doivent savoir utiliser le web ou google ... ;-)
Réponse
+0
moins plus
Ce site n'existe pas

matlab- 30 déc. 2004 à 11:22
resalut,

j'ai plus l'adresse exacte mais ça devait être un truc du style

www.algo_info.org/dijkstra.html

bonne journée
nabila- 22 juin 2007 à 20:29
bjr je recherche l'algorithme de plus cour chemin entre les ville d'algerie (algorithme de dijkstra
Réponse
+0
moins plus
Salut

Ce que tu cherches, c'est l'algorithme, ou un programme Matlab ?
Parce que je peux t'expliquer l'algo de Dijkstra (aussi appelé de Moore, si tu veux faire des recherches sur le net), mais ça n'a rien à voir avec Matlab (et pas grand-chose avec les matrices, mais c'est parce que matlab n'utilise que ça...) :

Le but est de trouver le chemin optimal dans un graphe valué.
Allez hop ! Je suis lancé -> c'est parti pour la théorie ;-)

graphe G=(X,U)
valuation U -> R
u ->v(u)
pb : Trouver dans G un chemin µ allant de AeX à BeX ("e" pour l'appartenance, bien sûr !) tq somme sur ueµ des v(u) soit optimale

Soit dit en passant : l'algorithme le plus classique s'appelle Bellman, mais j'imagine que t'as tes raisons pour vouloir Dijkstra

hypothèse supplémentaire : "c" une valuation, "s" un point de départ, et c: U -> R+ (pas de coût négatif)
On va noter P les sommets traités définitivement, T les sommets dont l'estimation est temporaires, Pi la fonction qui à un sommet associe le coût minimal pour y parvenir, A la fonction qui à un sommet associe son prédecesseur par le + court chemin.

Encore une hypothèse : Pi(x) = c(s,x) si (s,x)eU, mais infini sinon (initialement).

Initialement toujours, Pi(s)=0, P={s}, T=X\{s}, A(s)=epsilon (rien)

Algo :
Tant que T non vide faire
soit x0eT tq Pi(x0)=min des Pi(x) pour xeT
T=T\{x0}, P=P U(union) {x0}
Pour tout xeT faire
Si Pi(x)>Pi(x0)+c(x0,x) alors
Pi(x)=Pi(x0)+c(x0,x)
A(x)=x0
fin si
fin pour
fin TQ

On obtient dans Pi les valeurs des plus courts chemins pour chaque point d'arrivée, et pour retrouver le chemin, il suffit de remonter les A.
Le tout en un temps max égal au nb de sommets.

Bon courage pour le codage

Eléctions : Bush filled his SOUl with HOpe

spamware- 18 avril 2006 à 17:49
salut , es que tu peux m'aider a realiser l'algo de dijkstra en c tt ca en utilisant des matrices merci
ps: j'ai vraiment besoin d'aide
franky* 166Messages postés mardi 7 décembre 2004Date d'inscription 4 décembre 2008Dernière intervention - 19 avril 2006 à 09:48
Salut,

L'algorithme est déjà décrit dans les différents posts, il y a même le programme un peu plus bas...

Il y a quelque chose que tu n'as pas compris ? On ne peut t'aider que si tu poses des questions précises !
Réponse
+0
moins plus
En tout cas merci de te donner tant de mal mais j'avais déjà toutes ces infos et d'ailleurs j'ai commencé une ébauche sous matlab. J'arrive à avoir facilement une matrice représentant les coûts de chaque points par rapport aux points adjacents et je me suis inspiré des sites suivants :
http://www.europainternet.info/mmqos/index.php/Sujet/toms
http://fr.freepedia.org/Algorithme_de_Dijkstra.html
mais surtout de celui-ci :
http://icosaweb.ac-reunion.fr/Algorithmes/Graphes/Docs/AlgorithmeDijkstra.pdf
Mon problème est que je n'arrive pas à cumuler les coûts jusqu'à la balise. Voici mon code :

clear all
clc
a=[4 8 7 5 10;2 4 7 8 4;6 4 1 2 7;2 3 1 4 9;3 5 4 1 2];
disp(a);
dim=max(size(a));
absdepart=2; %abscisse balise de départ
orddepart=2; %ordonnée balise de départ
absarrivee=5; %abscisse balise de départ
ordarrivee=5; %ordonnée balise d'arrivée
for i=1:dim*dim
for j=1:dim*dim
b(i,j)=0;
end;
end;


% creation du vecteur comportant le nombre d'éléments
for k=1:dim*dim
numero(1,k)=k;
end;

abscisse=[];
ordonnee=[];
poids=[];
num=max(numero);

for i=1:dim
for j=1:dim
abscisse=[abscisse,i];
ordonnee=[ordonnee,j];
poids=[poids,a(i,j)];
end;
end;
% disp(poids);


% quel est le numero de la balise de départ dans le vecteur numero et
% affectation à numtest
for numtest=1:num
if abscisse(numtest)==absdepart
if ordonnee(numtest)==orddepart
break;
end;
end;
end;

% quel est le numero de la balise de fin dans le vecteur numero et
% affectation à numfin
for numfin=1:num
if abscisse(numfin)==absarrivee
if ordonnee(numfin)==ordarrivee
break;
end;
end;
end;

disp(numtest);
disp(numfin);
numero(1,numtest)=0;


% test de tous les points adjacents à la balise
for nbretest=1:num
if abscisse(nbretest)~=absdepart | ordonnee(nbretest)~=orddepart
if abs(abscisse(nbretest)-abscisse(numtest))<2
if abs(ordonnee(nbretest)-ordonnee(numtest))<2
%poidsmodif(nbretest)=poids(nbretest)+poids(numtest);
%b(numtest,nbretest)=poids(nbretest)+poids(numtest);
b(numtest,nbretest)=poids(nbretest);
%numero(1,nbretest)=0;
else
b(numtest,nbretest)=inf;
end;
else
b(numtest,nbretest)=inf;
end;
else
b(numtest,nbretest)=inf;
end;
end;


%test de tous les points adjacents aux précédents sauf balise et points
%adjacents précédents
for nbre=1:numfin
for nbretest=1:numfin
if b(nbretest,nbre)~=inf
if numero(nbretest)~=0
if abscisse(nbretest)~=abscisse(nbre) | ordonnee(nbretest)~=ordonnee(nbre)
if abs(abscisse(nbretest)-abscisse(nbre))<2
if abs(ordonnee(nbretest)-ordonnee(nbre))<2
b(nbre,nbretest)=poids(nbretest);
%numero(1,nbre)=0;
else
b(nbre,nbretest)=inf;
end;
else
b(nbre,nbretest)=inf;
end;
else
b(nbre,nbretest)=inf;
end;
else
b(nbre,nbretest)=inf;
end;
else
b(nbre,nbretest)=inf;
end;
end;
end;

disp(b);
disp(numero);



J'ai aussi récupérer celà mais je ne comprends pas le résultat obtenu :


function D = dijkstra(A,s,t)
% dijk - shortest paths from nodes 's' to nodes 't' using Dijkstra algorithm.
%
% D = dijk(A,s,t);
%
% A = n x n node-node weighted adjacency matrix of arc lengths
% (Note: A(i,j) = 0 => Arc (i,j) does not exist;
% A(i,j) = NaN => Arc (i,j) exists with 0 weight)
% s = FROM node indices
% = [] (default), paths from all nodes
% t = TO node indices
% = [] (default), paths to all nodes
% D = |s| x |t| matrix of shortest path distances from 's' to 't'
% = [D(i,j)], where D(i,j) = distance from node 'i' to node 'j'
%
% (If A is a triangular matrix, then computationally intensive node
% selection step not needed since graph is acyclic (triangularity is a
% sufficient, but not a necessary, condition for a graph to be acyclic)
% and A can have non-negative elements)
%
% (If |s| >> |t|, then DIJK is faster if DIJK(A',t,s) used, where D is now
% transposed and P now represents successor indices)
%
% (Based on Fig. 4.6 in Ahuja, Magnanti, and Orlin, Network Flows,
% Prentice-Hall, 1993, p. 109.)

% Copyright (c) 1998-2000 by Michael G. Kay
% Matlog Version 1.3 29-Aug-2000
%
% Modified by JBT, Dec 2000, to delete paths


% Input Error Checking ******************************************************
error(nargchk(1,3,nargin));

[n,cA] = size(A);

if nargin < 2 | isempty(s), s = (1:n)'; else s = s(:); end
if nargin < 3 | isempty(t), t = (1:n)'; else t = t(:); end

if ~any(any(tril(A) ~= 0)) % A is upper triangular
isAcyclic = 1;
elseif ~any(any(triu(A) ~= 0)) % A is lower triangular
isAcyclic = 2;
else % Graph may not be acyclic
isAcyclic = 0;
end

if n ~= cA
error('A must be a square matrix');
elseif ~isAcyclic & any(any(A < 0))
error('A must be non-negative');
elseif any(s < 1 | s > n)
error(['''s'' must be an integer between 1 and ',num2str(n)]);
elseif any(t < 1 | t > n)
error(['''t'' must be an integer between 1 and ',num2str(n)]);
end
% End (Input Error Checking) ************************************************

A = A'; % Use transpose to speed-up FIND for sparse A

D = zeros(length(s),length(t));
P = zeros(length(s),n);
for i = 1:length(s)
j = s(i);

Di = Inf*ones(n,1); Di(j) = 0;

isLab = logical(zeros(length(t),1));
if isAcyclic == 1
nLab = j - 1;
elseif isAcyclic == 2
nLab = n - j;
else
nLab = 0;
UnLab = 1:n;
isUnLab = logical(ones(n,1));
end

while nLab < n & ~all(isLab)
if isAcyclic
Dj = Di(j);
else % Node selection
[Dj,jj] = min(Di(isUnLab));
j = UnLab(jj);
UnLab(jj) = [];
isUnLab(j) = 0;
end

nLab = nLab + 1;
if length(t) < n, isLab = isLab | (j == t); end

[jA,kA,Aj] = find(A(:,j));
Aj(isnan(Aj)) = 0;

if isempty(Aj), Dk = Inf; else Dk = Dj + Aj; end

P(i,jA(Dk < Di(jA))) = j;
Di(jA) = min(Di(jA),Dk);

if isAcyclic == 1 % Increment node index for upper triangular A
j = j + 1;
elseif isAcyclic == 2 % Decrement node index for lower triangular A
j = j - 1;
end

%disp( num2str( nLab ));
end
D(i,:) = Di(t)';
end


encore merci de ton aide matlab

Réponse
+0
moins plus
function [p, pred] = dijkstra (n , C)
%n l'orde du graphe, C matrice des couts , p cout , pred : le chemin
S = 1 ;
T = 2 : n ;
p = C(1,:);
pred = Zeros (1,n);
T1 = find( ( C (1, :) > 0 & ( C(1,:)< Inf) )
pred(T1) = 1;
while( isempty(T) == 0 )
l = [ p(T)' T')
[m,e] = min ( l(:,1));
k = l(e,2);
S = [s,k];
T(e) = [] % supression du e eme element
T2 = find( ( C( k,:) > 0) & ( C ( k, : ) <Inf ) ) ;
for i : T3
if ( p(i ) > p(k) + C( k,i ) )
p( i ) = p( k ) + C (k,i ) ;
pred( i ) = k ;
end
end

end

end


je suis pas si sûr que ca :)

Ce document intitulé «  dijkstra  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes.

Le fait d'être membre vous permet d'avoir des options supplémentaires.