Implémentation de l'algorithme Dijkstra

Version imprimable

Bonsoir a tous
je veux implémenter l'algorithme Dijkstra sous matlab
je trouve ce code à l'internet et j'ai essayé de l'exécuter

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
function [sp, spcost] = dijkstra(matriz_costo, s, d)
% This is an implementation of the dijkstras algorithm, wich finds the 
% minimal cost path between two nodes. Its supoussed to solve the problem on 
% possitive weighted instances.
 
% the inputs of the algorithm are:
%farthestNode: the farthest node to reach for each node after performing
% the routing;
% n: the number of nodes in the network;
% s: source node index;
% d: destination node index;
 
%For information about this algorithm visit:
%http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
 
%This implementatios is inspired by the Xiaodong Wang's implememtation of
%the dijkstra's algorithm, available at
%http://www.mathworks.com/matlabcentral/fileexchange
%file ID 5550
 
%Author: Jorge Ignacio Barrera Alviar. April/2007
 
 
n=size(matriz_costo,1);
S(1:n) = 0;     %s, vector, set of visited vectors
dist(1:n) = inf;   % it stores the shortest distance between the source node and any other node;
prev(1:n) = n+1;    % Previous node, informs about the best previous node known to reach each  network node 
 
dist(s) = 0;
 
 
while sum(S)~=n
    candidate=[];
    for i=1:n
        if S(i)==0
            candidate=[candidate dist(i)];
        else
            candidate=[candidate inf];
        end
    end
    [u_index u]=min(candidate);
    S(u)=1;
    for i=1:n
        if(dist(u)+matriz_costo(u,i))<dist(i)
            dist(i)=dist(u)+matriz_costo(u,i);
            prev(i)=u;
        end
    end
end
 
 
sp = [d];
 
while sp(1) ~= s
    if prev(sp(1))<=n
        sp=[prev(sp(1)) sp];
    else
        error;
    end
end;
spcost = dist(d);

Mais j'ai obtenu cet erreur:

??? Input argument "matriz_costo" is undefined.

Error in ==> dijkstra at 24
n=size(matriz_costo,1);

pouvez vous m'aider svp
cordialement

09/05/2016, 19h47
Jerome Briot

Lire la FAQ : Input argument *** is undefined.
09/05/2016, 19h52
zeinab ali

Citation:

Envoyé par Jerome Briot

Lire la FAQ : Input argument *** is undefined.

il est un input argument comment je vais le définir?
10/05/2016, 11h04
le fab

Salut

Citation:

Envoyé par zeinab ali

je trouve ce code à l'internet et j'ai essayé de l'exécuter

comment as tu essayé de l'exécuter ??
10/05/2016, 11h32
zeinab ali

Citation:

Envoyé par le fab

Salut

comment as tu essayé de l'exécuter ??

salut
j'ai essayé de l'exécuter avec le logiciel matlab
11/05/2016, 13h17
le fab

certes, mais comment ?

1 pièce(s) jointe(s)

Bonjour

voici un exemple simple d'utilisation de fonctions :

Dans un fichier nommé stat.m, on écrit le texte suivant Dans un fichier nommé stat.m
Etape 1 : Création de la fonction
Code:

1 2 3 4 function [mean,stdev] = stat(x) n = length(x); mean = sum(x)/n; stdev = sqrt(sum((x-mean).^2/n));
Etape 2 : Création d'un script qui utilise la fonction :
Dans un fichier nommé monscript.m (qui se trouve dans le même répertoire que stat.m), on écrit le texte suivant :

Code:

[mean stdev] = stat([12.7 45.4 98.9 26.6 53/1])

pour vous ce qui manque c'est la deuxième étape , il faut un programme principale qui appele cette fonction .
qui se trouve dans le même répertoire que main.m
Code:

1 2 3 4 5 6 7 8 9 10 11 s= 1; % par exemple la source = 1 d= 4; % par exemple destination = 4 matriz_costo = [0 8 0 0 11 0 0; 0 0 2 0 0 0 0 ; 0 0 0 5 0 0 14; 0 0 0 0 3 0 0; 11 0 0 0 0 2 0; 0 0 0 7 0 0 9; 0 6 0 0 0 0 0 ;]; % je n'ai pas lu l code mais je pense c'est la matrice de distances . [sp, spcost] = dijkstra(matriz_costo, s, d)
Je vous donne un autre code plus simple , si tu n'as pas compris je peux t'expliquer le code .