Dijkstra

www.algoinfo.org/dijkstra.html

Merci quand même mais à chercher algo-info ou algoinfo ou .... je risque d'y passer beaucoup de temps

Ce site n'existe pas

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

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

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 :)