调度引擎>> Using-Dijkstras-Algorithm-with-OpenMP>> 返回
项目作者： emrecantural

项目描述 ：
In this project, we will use the algorithm we learned in the Graph Theory course: Dijkstra's Algorithm. The main purpose of the algorithm is to find the shortest path on Graf.
高级语言： C++
项目地址: git://github.com/emrecantural/Using-Dijkstras-Algorithm-with-OpenMP.git


In this project, we will use the algorithm we learned in the Graph Theory course: Dijkstra’s Algorithm.
The main purpose of the algorithm is to find the shortest path on Graf.

As the way of working:

  1. Set the starting point.
  2. Determine the cost from the starting point to the other points and mark the low cost point.
  3. Repeat the same process among other points that can be reached from the point marked in the second step.

The program uses the matrix during the run. The matrix to be used is as follows.

N 1 2 3 4 5 6 7 8
1 0 40 15 Inf Inf Inf 35 Inf
2 40 0 0 100 Inf Inf 25 Inf
3 15 0 0 20 10 50 Inf 50
4 Inf 100 20 0 10 Inf 45 Inf
5 Inf Inf 10 10 0 30 50 30
6 Inf Inf 50 Inf 30 0 Inf 0
7 35 25 Inf 45 50 Inf 0 0
8 Inf Inf 50 Inf 30 0 0 0

Creates a tree while the algorithm is running. Initially, a node is selected and calculation is made according to this node.
Connection status is specified with connected [0] = true. Then values are used with mind[i].
The purpose is to produce results using these matrix values in the algorithm.

Necessary libraries for the program.

  1. #include <iostream>
  2. #include <ctime>
  3. #include <cstdlib>
  4. #include <iomanip>
  5. using namespace std;
  6. # define NV 9
  7. int main(int argc, char** argv);
  8. int* dijkstra_distance(int ohd[NV][NV]);
  9. void find_nearest(int mind[NV], bool connected[NV], int* d, int* v);
  10. void init(int ohd[NV][NV]);
  11. void update_mind(int mv, bool connected[NV], int ohd[NV][NV], int mind[NV]);

The main function of the program.

  1. int main(int argc, char** argv)
  2. {
  3.     int i;
  4.     int i4_huge = 2147483647;
  5.     int j;
  6.     int* mind;
  7.     int ohd[NV][NV];
  8.     cout << "\n";
  9.     cout << "  Finding the minimum distance between nodes by applying the Dijkstra algorithm on the distance matrix.\n";
  10.     cout << "  Prepared by Emre Can TURAL\n\n";
  12.     /*First of all, we need to initialize the  data matrix to be used.
  13.     The matrix to be used is defined by a two-dimensional array in the "init" function.*/
  14.     init(ohd);
  16.     /*The matrix used is printed on the screen as a table with the following codes.
  17.     The values of the two-dimensional array are used for this output.*/
  18.     cout << "\n";
  19.     cout << "  Distance matrix:\n";
  20.     cout << "\n";
  21.     cout << "        1    2     3     4     5     6      7    8";
  22.     cout << "\n";
  23.     cout << "\n";
  24.     for (i = 1; i < NV; i++)
  25.     {
  26.         cout << "  " << i;
  27.         for (j = 1; j < NV; j++)
  28.         {
  29.             if (ohd[i][j] == i4_huge)
  30.             {
  31.                 cout << "   Inf";
  32.             }
  33.             else
  34.             {
  35.                 cout << "   " << setw(3) << ohd[i][j];
  36.             }
  37.         }
  38.         cout << "\n";
  39.         cout << "\n";
  40.     }

The other part of the screen output is the results. Distances must be calculated for the results. For this purpose, the function “dijkstra_distance” is used.

  1.     mind = dijkstra_distance(ohd);

The results obtained by calculations are written on the screen in this section.

  1.     cout << "\n";
  2.     cout << "  Minimum distances from node 1:\n";
  3.     cout << "\n";
  4.     for (i = 1; i < NV; i++)
  5.     {
  6.         cout << "  " << setw(2) << i
  7.             << "  " << setw(2) << mind[i] << "\n";
  8.     }
  9.     cout << "\n";
  10.     cout << "\n";
  11.     delete[] mind;
  12.     system("pause");
  13.     return 0;
  14. }

The “init” function uses the matrix we created.There are values that we will use in this matrix. The function uses the two-dimensional array as “int ohd [NV] [NV]”. Makes calculations according to the limit value of 2147483647. The purpose of this is to prevent the overflow of int value.

  1. void init(int ohd[NV][NV])
  2. {
  3.     int i;
  4.     int i4_huge = 2147483647;
  5.     int j;
  7.     for (i = 1; i < NV; i++)
  8.     {
  9.         for (j = 1; j < NV; j++)
  10.         {
  11.             if (i == j)
  12.             {
  13.                 ohd[i][i] = 0;
  14.             }
  15.             else
  16.             {
  17.                 ohd[i][j] = i4_huge;
  18.             }
  19.         }
  20.     }
  21.     ohd[1][2] = ohd[2][1] = 40;
  22.     ohd[1][3] = ohd[3][1] = 15;
  23.     ohd[1][7] = ohd[7][1] = 35;
  24.     ohd[2][3] = ohd[3][2] = 0;
  25.     ohd[2][4] = ohd[4][2] = 100;
  26.     ohd[2][7] = ohd[7][2] = 25;
  27.     ohd[3][4] = ohd[4][3] = 20;
  28.     ohd[3][5] = ohd[5][3] = 10;
  29.     ohd[3][6] = ohd[6][3] = 50;
  30.     ohd[3][8] = ohd[8][3] = 50;
  31.     ohd[4][5] = ohd[5][4] = 10;
  32.     ohd[4][7] = ohd[7][4] = 45;
  33.     ohd[5][6] = ohd[6][5] = 30;
  34.     ohd[5][7] = ohd[7][5] = 50;
  35.     ohd[5][8] = ohd[8][5] = 30;
  36.     ohd[6][8] = ohd[8][6] = 0;
  37.     ohd[7][8] = ohd[8][7] = 0;
  38.     return;
  39. }

Distances between nodes are calculated with the “dijkstra_distance” function. First node must be specified for the startup process. The process of starting the project depends on this node.

  1. int* dijkstra_distance(int ohd[NV][NV])
  2. {
  3.     //The creation of nodes begins with this step.
  4.     bool* connected;
  5.     connected = new bool[NV];
  6.     connected[0] = true;
  8.     int i;
  9.     for (i = 1; i < NV; i++)
  10.     {
  11.         connected[i] = false;
  12.     }
  14.     //In the next steps, each node is used step by step.
  15.     int md;
  16.     int* mind;
  17.     int mv;
  18.     mind = new int[NV];
  19.     for (i = 1; i < NV; i++)
  20.     {
  21.         mind[i] = ohd[1][i];
  22.     }

Continue with iteration. Add one node to each regeneration of the function used.First, find the nearest unconnection node. Mark this node as connected.After determining the minimum distance to the MV node, see if this reduces the minimum distance to other nodes.

  1.     int step;
  2.     for (step = 1; step < NV; step++)
  3.     {
  4.         //The "find_nearest" function is used for the nearest node.
  5.         find_nearest(mind, connected, &md, &mv);
  7.         //In this section, the connection is checked.
  8.         if (mv == -1)
  9.         {
  10.             cout << "\n";
  11.             cout << "Warning! Graph not be connected\n";
  12.             break;
  13.         }
  14.         connected[mv] = true;
  16.         //The "update_mind" function is used to update the value.
  17.         update_mind(mv, connected, ohd, mind);
  18.     }
  19.     delete[] connected;
  20.     return mind;
  21. }

find_nearest finds the nearest unconnected node.Thus, the value to be marked is determined.

  1. void find_nearest(int mind[NV], bool connected[NV], int* d, int* v)
  2. {
  3.     int i;
  4.     int i4_huge = 2147483647;
  6.     *d = i4_huge;
  7.     *v = -1;
  8.     for (i = 0; i < NV; i++)
  9.     {
  10.         if (!connected[i] && mind[i] < *d)
  11.         {
  12.             *d = mind[i];
  13.             *v = i;
  14.         }
  15.     }
  16.     return;
  17. }

update_mind updates the minimum distance vector. This update is done according to the 2147483647 limit.
We use this value for infinity. Because integer values have a limit.

  1. void update_mind(int mv, bool connected[NV], int ohd[NV][NV], int mind[NV])
  3. {
  4.     int i;
  5.     const int i4_huge = 2147483647;
  7.     for (i = 1; i < NV; i++)
  8.     {
  9.         if (!connected[i])
  10.         {
  12.             if (ohd[mv][i] < i4_huge)
  13.             {
  14.                 if (mind[mv] + ohd[mv][i] < mind[i])
  15.                 {
  16.                     mind[i] = mind[mv] + ohd[mv][i];
  17.                 }
  18.             }
  19.         }
  20.     }
  21.     return;
  22. }