Discussion :

[camelia136]

Bonjour

depuis ce matin j'essaye de trouver une solution à mon problème mais je n'arrive pas

je souhaite calculer le plus court chemin entre 2 noeud mais j'ai envie qu' à chaque fois que je lance mon programme il me donne une distance différente pour les même 2 noeuds.

j'ai essayé de multiplier le code concerné par un random comme ça à chaque fois il me donne une valeur différente mais ça n'a pa marché car à chaque fois j'ai la même distance

Avez vous une idée de comment je pourrais faire ?

[duf42]

Bonjour,

Pourrais-tu nous montrer ton code?

Pourquoi souhaites-tu avoir une distance différente à chaque fois? Si tu calcules la distance la plus courte entre 2 points celle-ci doit être unique, non?

Duf

[camelia136]

en fait ce n'est pas la notion de distance qui m’intéresse vraiment , c'est plutôt le poids que je calcule à partir d'une fonction.
mais pour simplifier les choses j'ai choisi de travailler avec la distance , j'ai envie d'avoir à chaque fois que je lance mon programme des valeur de distances aléatoire ( une mise à jour des distances)
mais par contre les noeuds doivent restés fixes.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
function [dist,path] = dijkstra(nodes,segments,start_id,finish_id)
 
 
 
if (nargin < 3) % SETUP
    % (GENERATE RANDOM EXAMPLE OF NODES AND SEGMENTS IF NOT GIVEN AS INPUTS)
    % Create a random set of nodes/vertices,and connect some of them with
    % edges/segments. Then graph the resulting map.
 
 num_nodes = 40; L = 100; max_seg_length = 30; ids = (1:num_nodes)';
 
 
valeur_init =2; 
rand('seed',valeur_init); % initialisation
rand(num_nodes,2)    % Generate a random set of number
 
rand('seed',valeur_init); % ré-initialisation
 
nodes = [ids L*rand(num_nodes,2)]; % create random nodes
h = figure; plot(nodes(:,2),nodes(:,3),'k.') % plot the nodes
 
    text(nodes(num_nodes,2),nodes(num_nodes,3),...
        [' ' num2str(ids(num_nodes))],'Color','b','FontWeight','b')
    hold on
    num_segs = 0; segments = zeros(num_nodes*(num_nodes-1)/2,3);
 
    for i = 1:num_nodes-1 % create edges between some of the nodes
        text(nodes(i,2),nodes(i,3),[' ' num2str(ids(i))],'Color','b','FontWeight','b')
        for j = i+1:num_nodes
            d = sqrt(sum((nodes(i,2:3) - nodes(j,2:3)).^2));
 
 
            if and(d < max_seg_length,rand < 1)
                plot([nodes(i,2) nodes(j,2)],[nodes(i,3) nodes(j,3)],'k.-')
                % add this link to the segments list
                num_segs = num_segs + 1;
                segments(num_segs,:) = [num_segs nodes(i,1) nodes(j,1)];
            end
        end
    end
    segments(num_segs+1:num_nodes*(num_nodes-1)/2,:) = [];
    axis([0 L 0 L])
 
 
    % Calculate Shortest Path Using Dijkstra's Algorithm
    % Get random starting/ending nodes,compute the shortest distance and path.
 
 
 
prompt = {'Enter starting node:','Enter ending node:'};
dlg_title = 'Get starting/ending nodes';
num_lines = 1;
def = {'',''};
answer = inputdlg(prompt,dlg_title,num_lines,def);
 
if isempty(answer)
    return
end
 
start_id = str2double(answer{1});
disp(['start id = ' num2str(start_id)]);
finish_id = str2double(answer{2});
disp(['finish id = ' num2str(finish_id)]);
 
 
 
 
 
    [distance,path] = dijkstra(nodes,segments,start_id,finish_id);
 
    disp(['distance = ' num2str(distance)]); disp(['path = [' num2str(path) ']']);
 
 
    % If a Shortest Path exists,Plot it on the Map.
 
 
    figure(h)
    for k = 2:length(path)
        m = find(nodes(:,1) == path(k-1));
        n = find(nodes(:,1) == path(k));
        plot([nodes(m,2) nodes(n,2)],[nodes(m,3) nodes(n,3)],'ro-','LineWidth',2);
    end
    title(['Shortest Distance from ' num2str(start_id) ' to ' ...
        num2str(finish_id) ' = ' num2str(distance)])
    hold off
 
else %--------------------------------------------------------------------------
    % MAIN FUNCTION - DIJKSTRA'S ALGORITHM
 
    % initializations
    node_ids = nodes(:,1);
    [num_map_pts,cols] = size(nodes);
    table = sparse(num_map_pts,2);
    shortest_distance = Inf(num_map_pts,1);
    settled = zeros(num_map_pts,1);
    path = num2cell(NaN(num_map_pts,1));
    col = 2;
    pidx = find(start_id == node_ids);
    shortest_distance(pidx) = 0;
    table(pidx,col) = 0;
    settled(pidx) = 1;
    path(pidx) = {start_id};
    if (nargin < 4) % compute shortest path for all nodes
        while_cmd = 'sum(~settled) > 0';
    else % terminate algorithm early
        while_cmd = 'settled(zz) == 0';
        zz = find(finish_id == node_ids);
    end
    while eval(while_cmd)
        % update the table
        table(:,col-1) = table(:,col);
        table(pidx,col) = 0;
        % find neighboring nodes in the segments list
        neighbor_ids = [segments(node_ids(pidx) == segments(:,2),3);
            segments(node_ids(pidx) == segments(:,3),2)];
        % calculate the distances to the neighboring nodes and keep track of the paths
        for k = 1:length(neighbor_ids)
            cidx = find(neighbor_ids(k) == node_ids);
            if ~settled(cidx)
 
                d = sqrt(sum((nodes(pidx,2:cols) - nodes(cidx,2:cols)).^2));
 
 
 
                if (table(cidx,col-1) == 0) || ...
                        (table(cidx,col-1) > (table(pidx,col-1) + d))
                    table(cidx,col) = table(pidx,col-1) + d;
                    tmp_path = path(pidx);
                    path(cidx) = {[tmp_path{1} neighbor_ids(k)]};
                else
                    table(cidx,col) = table(cidx,col-1);
                end
            end
        end
        % find the minimum non-zero value in the table and save it
        nidx = find(table(:,col));
        ndx = find(table(nidx,col) == min(table(nidx,col)));
        if isempty(ndx)
            break
        else
            pidx = nidx(ndx(1));
            shortest_distance(pidx) = table(pidx,col);
            settled(pidx) = 1;
        end
    end
    if (nargin < 4) % return the distance and path arrays for all of the nodes
        dist = shortest_distance';
        path = path';
    else % return the distance and path for the ending node
        dist = shortest_distance(zz);
        path = path(zz);
        path = path{1};
    end
end

la bout de code pour calculer la distance

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

d = sqrt(sum((nodes(pidx,2:cols) - nodes(cidx,2:cols)).^2));

du coup je peux même ne pas utiliser la notion de distance prendre n'importe qu'elle valeur et trouver le chemins les plus court à partir de ces valeurs