Use Dijkstra’s algorithm and draw the routing graphs for each iteration by indic

Question

Use Dijkstra’s algorithm and draw the routing graphs for each iteration by indicating the extended source and weight for each nodes.

Code:
%routing algorithm
clear all; close all;
N=7;
rand("seed",123456);
x=randi([10, 90],1,N);
y=randi([10, 90],1,N);
x(1)=0;y(1)=0;
x(N)=100;
y(N)=100;
figure
plot(x(2:N-1),y(2:N-1),"o","markersize",15,"markerfacecolor","k");
hold on;
plot([x(1) x(N)],[y(1) y(N)],"s","markersize",15,"markerfacecolor","b");
grid on;
for i=1:N
text(x(i),y(i)+5,strcat("N",num2str(i)));
endsource=[1];
dest=[2:N];
w=ones(1,N)*inf;
w(1)=0;
d=[];
for i=1:length(dest)
j=dest(i);
for k=1:length(source)
l=source(k);
dd=sqrt((x(j)-x(l))^2+(y(j)-y(l))^2);
if dd>601
dd=inf;
end
d(i,k)=dd+w(l);
end
end
dim=size(d);
if dim(2)~=1
d=min(d');
end
[md,idx]=min(d);
j=dest(idx);
plot(x(j),y(j),"rs","markersize",20,"linewidth",1.5);
text(x(j),y(j)-5,num2str(md));
source=[source j];
dest(idx)=[];
w(j)=md;
pause(1);

Explanation / Answer

#include <stdio.h>

#include <limits.h>

#define V 9

int minDistance(int dist[], bool sptSet[])

{

   // Initialize min value

   int min = INT_MAX, min_index;

   for (int v = 0; v < V; v++)

     if (sptSet[v] == false && dist[v] <= min)

         min = dist[v], min_index = v;

   return min_index;

}

// A utility function to print the constructed distance array

int printSolution(int dist[], int n)

{

   printf("Vertex   Distance from Source ");

   for (int i = 0; i < V; i++)

      printf("%d tt %d ", i, dist[i]);

}

void dijkstra(int graph[V][V], int src)

{

     int dist[V];     // The output array. dist[i] will hold the shortest

                      // distance from src to i

     bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest

                     // path tree or shortest distance from src to i is finalized

     for (int i = 0; i < V; i++)

        dist[i] = INT_MAX, sptSet[i] = false;

     // Distance of source vertex from itself is always 0

     dist[src] = 0;

     // Find shortest path for all vertices

     for (int count = 0; count < V-1; count++)

     {

       int u = minDistance(dist, sptSet);

       // Mark the picked vertex as processed

       sptSet[u] = true;

       for (int v = 0; v < V; v++)

         if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX

                                       && dist[u]+graph[u][v] < dist[v])

            dist[v] = dist[u] + graph[u][v];

     }

     // print the constructed distance array

     printSolution(dist, V);

}

int main()

{

   /* Let us create the example graph discussed above */

   int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},

                      {4, 0, 8, 0, 0, 0, 0, 11, 0},

                      {0, 8, 0, 7, 0, 4, 0, 0, 2},

                      {0, 0, 7, 0, 9, 14, 0, 0, 0},

                      {0, 0, 0, 9, 0, 10, 0, 0, 0},

                      {0, 0, 4, 14, 10, 0, 2, 0, 0},

                      {0, 0, 0, 0, 0, 2, 0, 1, 6},

                      {8, 11, 0, 0, 0, 0, 1, 0, 7},

                      {0, 0, 2, 0, 0, 0, 6, 7, 0}

                     };

    dijkstra(graph, 0);

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.