C++ Dijkstra's algorithm on a simple 10x10 map help please.

[SwissProgrammer]

Hello. I have been studying Dijkstra's algorithm. It looks like every example of its use (that I found) is in a CLI program.

Is there an example, that I can study and modify, of a small map (10 squares by 10 squares)? I would like to be able to weight each square and graphically see the result.

Just C++ please. No Visual C++.

Thank you.

Using the following graphic.

[Banfa]

Have you considered trying to implement it directly from its description or pseudo code e.g. as given at Wikipedia?

[Banfa]

Or try this

[SwissProgrammer]

Banfa,

It looks like you supplied mathematical logic that I can use for this.

It looks like you supplied C++ code that I can learn from.

I am studying this now.

Best answer.

Thank you.

[SwissProgrammer]

I am still lost in the logic of how to apply Dijkstra's algorithm in C++ via a GUI.

I have been going through this various different ways and I decided to write it out one step at a time then convert that to C++.

I posted the following example elsewhere, and I am waiting on a reply.

I do not like to post to two sites the same question, but here it is. Maybe you guys could help:



I have a 10 by 10 grid that I want to use for a game and I have the following that I have written. It has become complicated. Now I want to use vectors in simplifying this code.

I have been studying vectors and arrays. I tried using arrays and it became so complicated that I am now trying to use vectors.

I can set up my WinMain and use CreateWindowExW to put text into for seeing a report of what I am doing. I can do that. I do not want to use CLI. I want help with placing the following into vectors and simplifying the code.

Would you please clean this up and use vectors? I can then try to use your logic further in the program.

C++11 please.

I want to be able to expand this to a larger size maybe 50 by 50, or 100 by 100, etc. Thus I want to automate it and not have to write out every one of the lines again and again.

Thank you.

// I wrote this in WordPad and then used CodeBlocks 17.12 for formatting to show on [...].
 
// I am Very Much a Beginner !
 
// This is in a GUI, not a CLI program.
 
// 10 by 10 grid.
 
// Each grid square is one pixel by one pixel (for mathematical simplicity for now). This can be enlarged later.
 
// Each grid square has a weight to resist game character movement.
 
// Each move can be in 8 different directions
    // up left      x = x -1    y = y -1    diagonal move
    // up           x = x       y = y -1     
    // up right     x = x +1    y = y -1    diagonal move
    // right        x = x +1    y = y
    // down right   x = x +1    y = y +1    diagonal move
    // down         x = x       y = y +1
    // down left    x = x -1    y = y +1    diagonal move
    // left         x = x -1    y = y
 
// There are conditions that must be met BEFORE being allowed to move.
 
/// After each one move is made, it is to be saved to a string that contains
///    a listing of each square that was passed through (x and y positions).
/// Or if someone suggests a better way and shows me some code to do that, thank you.
 
 
   //Step 1.) initialize x and y starting point and ending point.
 
int x = startingX;   //Starting X
int y = startingY;   //Starting Y
int Ex = endingX;    //Ending X
int Ey = endingY;    //Ending Y
 
// Until changed set the initial Weight =1
int Weight =1;
 
int MaximumX = 10;
int MaximumY = 10;
 
int ThisTotaledWeight = 0;
 
int ShortestPath=9999;
 
 
      // IF x = Ex and if y = Ey
      // {
            // No path to follow.
            // Beginning and Ending locations are the same.
            // Maybe put a notice of something like "no path to follow.".
            // Maybe have the worker or person or etc. to respond verbally.
            // Maybe return notification that path length is zero.
            // Get out of this process.
      // }
 
 
 
   //Step 2.) move distance 0 from beginning.
   //Get the weight of   (startingX),   (startingY).
   //Since it is the beginning and no moves have been made, weight of   (startingX),   (startingY) = 0 .
   //Therefore ThisTotaledWeight = 0;
   //MovesSoFar = 0;
string s0000 = "MovesSoFar=0, ThisTotaledWeight,    (startingX),   (startingY)";
 
 
/*
   //Step 3.) move distance 1 from beginning.
   //   Apply these conditions:
      //   Can NOT move into a 999 square.
      //   Can NOT move into a previously used square.
         //Previously used squares:
         //   (startingX, startingY)
      //   Can NOT move into a square that is beside of a previously used square.
         //Squares that is beside of a previously used square:
         //   None.
 
 
      // IF the previous conditions are not a problem, then do the following:
         {
            //Get the weight of    (startingX)-1,   (startingY)-1
            //   Add that weight to ThisTotaledWeight from string s000.
            //   Since a move of x-1 and y-1 is a diagonal move, add .0001 to the ThisTotaledWeight .
         }
 
      // IF   (startingX),   (startingY)-1   is the end location
            //      meaning that   (startingX)=Ex   and   (startingY)-1=Ey,
         {
            // IF ShortestPath>ThisTotaledWeight,
               {
                  // then
                  // ShortestPath=ThisTotaledWeight;
               }
            // ELSE IF ShortestPath=ThisTotaledWeight,
               {
                  // then
                  string s000_0001 = "MovesSoFar=1 & ThisTotaledWeight &   Move0 (startingX)   (startingY)   &   Move1 (startingX)-1   (startingY)-1 ";
               }
         }
      // ELSE IF   (startingX),   (startingY)-1   is NOT the end location
            //      meaning that both   (startingX) != Ex   and   (startingY)-1 != Ey,
         {
            // IF ShortestPath<ThisTotaledWeight,
               {
                  // then
                  string s000_0001 = "999";
               }
            // ELSE IF ShortestPath=ThisTotaledWeight,
               {
                  // then
                  string s000_0001 = "999";
               }
            // ELSE IF ShortestPath>ThisTotaledWeight,   such as it being still at 9999.
               {
                  // then
                  string s000_0001 = "MovesSoFar=1 & ThisTotaledWeight &   Move0 (startingX)   (startingY)   &   Move1 (startingX)-1   (startingY)-1 ";
               }
         }
 
*/
 
 
 
 
 
      //   IF the previous conditions are not a problem, then do the following:
         //Get the weight of    (startingX),      (startingY)-1
         //   Add that weight to ThisTotaledWeight from string s000.
         // Etc.
         string s000_0002 = "MovesSoFar=1, ThisTotaledWeight,   (startingX),      (startingY)-1";
 
      //   If the previous conditions are not a problem, then do the following:
         //Get the weight of    (startingX)+1,  (startingY)-1
         //   Add that weight to ThisTotaledWeight from string s000.
         //   Since a move of x+1 and y-1 is a diagonal move, add .0001 to the ThisTotaledWeight .
         // Etc.
         string s000_0003 = "MovesSoFar=1, ThisTotaledWeight,   (startingX)+1,  (startingY)-1";
 
      //   If the previous conditions are not a problem, then do the following:
         //Get the weight of    (startingX)+1,  (startingY)
         //   Add that weight to ThisTotaledWeight from string s000.
         // Etc.
         string s000_0004 = "MovesSoFar=1, ThisTotaledWeight,   (startingX)+1,  (startingY)";
 
      //   If the previous conditions are not a problem, then do the following:
         //Get the weight of    (startingX)+1,  (startingY)+1
         //   Add that weight to ThisTotaledWeight from string s000.
         //   Since a move of x+1 and y+1 is a diagonal move, add .0001 to the ThisTotaledWeight .
         // Etc.
         string s000_0005 = "MovesSoFar=1, ThisTotaledWeight,   (startingX)+1,  (startingY)+1";
 
      //   If the previous conditions are not a problem, then do the following:
         //Get the weight of    (startingX),      (startingY)+1
         //   Add that weight to ThisTotaledWeight from string s000.
         // Etc.
         string s000_0006 = "MovesSoFar=1, ThisTotaledWeight,   (startingX),      (startingY)+1";
 
      //   If the previous conditions are not a problem, then do the following:
         //Get the weight of    (startingX)-1,   (startingY)+1
         //   Add that weight to ThisTotaledWeight from string s000.
         //   Since a move of x-1 and y+1 is a diagonal move, add .0001 to the ThisTotaledWeight .
         // Etc.
         string s000_0007 = "MovesSoFar=1, ThisTotaledWeight,   (startingX)-1,   (startingY)+1";
 
      //   If the previous conditions are not a problem, then do the following:
         //Get the weight of    (startingX)-1,   (startingY)
         //   Add that weight to ThisTotaledWeight from string s000.
         // Etc.
         string s000_0008 = "MovesSoFar=1, ThisTotaledWeight,   (startingX)-1,   (startingY)";
 
 
 
   //Step 4.) move distance 2 from beginning.
   //   These all start at s0001   which is  x=(startingX)-1   and   y=(startingY)-1
   //   Can NOT move into a square that either x or y are less than zero.
   //   Can NOT move into a square that either x or y are larger than the maximum value for each.
   //   Can NOT move into a 999 square.
   //   Can NOT move into a previously used square.
      //Previously used squares:
      //   (startingX, startingY)
   //   Can NOT move into a square that is beside of a previously used square.
      //Squares that is beside of a previously used square:
      //   (startingX),   (startingY);
      //   (startingX)-1,   (startingY)-1;
      //   (startingX),      (startingY)-1;
      //   (startingX)+1,  (startingY)-1;
      //   (startingX)+1,  (startingY);
      //   (startingX)+1,  (startingY)+1;
      //   (startingX),      (startingY)+1;
      //   (startingX)-1,   (startingY)+1;
      //   (startingX)-1,   (startingY);
 
 
// Un-modified for conditionals:
// string s000_0001_0001 = "MovesSoFar=2,   (startingX)-1,   (startingY)-1   &   (startingX)-1-1,   (startingY)-1-1";
// string s000_0001_0002 = "MovesSoFar=2,   (startingX)-1,   (startingY)-1   &   (startingX)-1,      (startingY)-1-1";
// string s000_0001_0003 = "MovesSoFar=2,   (startingX)-1,   (startingY)-1   &   (startingX)-1+1,  (startingY)-1-1";
// string s000_0001_0004 = "MovesSoFar=2,   (startingX)-1,   (startingY)-1   &   (startingX)-1+1,  (startingY)-1";
// string s000_0001_0005 = "MovesSoFar=2,   (startingX)-1,   (startingY)-1   &   (startingX)-1+1,  (startingY)-1+1";
// string s000_0001_0006 = "MovesSoFar=2,   (startingX)-1,   (startingY)-1   &   (startingX)-1,      (startingY)-1+1";
// string s000_0001_0007 = "MovesSoFar=2,   (startingX)-1,   (startingY)-1   &   (startingX)-1-1,   (startingY)-1+1";
// string s000_0001_0008 = "MovesSoFar=2,   (startingX)-1,   (startingY)-1   &   (startingX)-1-1,   (startingY)-1";
 
 
// The following IS Modified for conditionals:
 
   ///   Can NOT move into a square that either x or y are less than zero.
      //      If the location   x=(startingX)-1-1   is   >=0
      //      and
      //      If the location   y=(startingY)-1-1   is   >=0
      //         Then proceed to next conditional.
 
 
   ///   Can NOT move into a square that either x or y are larger than the maximum value for each.
      //      If the location   x=(startingX)-1-1   is   <=MaximumX
      //      and
      //      If the location   y=(startingY)-1-1   is   <=MaximumY
      //         Then proceed to next conditional.
 
 
   ///   Can NOT move into a 999 square.
      //      If the location   x=(startingX)-1-1   and   y=(startingY)-1-1   has a Weight < 999
      //         Then proceed to next conditional.
 
 
   ///   Can NOT move into a previously used square.
      //   If the location   x=(startingX)-1-1   and   y=(startingY)-1-1   is not a part of the list of
         //   From Move 0:
            //   (startingX),   (startingY);
         //   From Move 1:
            //   (startingX)-1,   (startingY)-1;
            //   (startingX),      (startingY)-1;
            //   (startingX)+1,  (startingY)-1;
            //   (startingX)+1,  (startingY);
            //   (startingX)+1,  (startingY)+1;
            //   (startingX),      (startingY)+1;
            //   (startingX)-1,   (startingY)+1;
            //   (startingX)-1,   (startingY)";
 
   ///   Then do this:
 
      //   If the previous conditions are not a problem, then do the following:
         //Get the weight of    (startingX),      (startingY)-1
         //   Add that weight to ThisTotaledWeight from string s000_0001.
         //   Since a move of x-1 and y-1 is a diagonal move, add .0001 to the ThisTotaledWeight .
         string s000_0001_0001 = "MovesSoFar=2, ThisTotaledWeight=2,   Move0 (startingX),   (startingY)   &   Move1 (startingX)-1,   (startingY)-1   &   Move2 (startingX)-1-1,   (startingY)-1-1";
 
   //   Else   string s000_0001_0001="999";.
 
// Continue...
 
//   When complete, save all of this into a text file to be able to read and to examine.
 
//   When complete, list all of the strings that have a ThisTotaledWeight as lowest value and then save this into another text file to be able to read and to examine.
 
 
 

I have been struggling with this, occasionally, for weeks and it is interrupting my life. I think that I now have at least the conditionals in place. But, I am having great difficulty in condensing it in such a manner that the map can be other than 10x10.

Please help !

[SwissProgrammer]

Glory to God now I can use C++ vectors.

Wow! And to think that at some time Stroustrup held all that stuff (new!) in his mind and had to explain it as new concepts step by step to some consortium that came up with programming rules for code that they did not even design.

Some C++ concepts I have had difficulty with. (Ok, lots of them!)

I read previous posts here on bytes.com and more at https://www.bitdegree.org/learn/c-plus-plus-vector and https://www.tutorialspoint.com/cpp_s...ary/vector.htm and other pages. Using an online compiler I now have an example of vector applications with notes that I can reference.

But, I still have had difficulty condensing the previous code.

I really am new at C++ and it really has been intensely difficult for me.


If I get help with condensing the previous post's code thank you.

[SwissProgrammer]

I am still struggling with condensing that code.

Help. Please help.

[SwissProgrammer]

Here is my latest attempt.


Example:
Grid x and y
x = 10 horizontal count.
y = 10 vertical count.

weights as follows with A and B representing the Start A and the Finish B:

1.....1.....1.....5.....1.....1.....1.....1.....1. ....1

1.....1.....1.....5.....1.....1.....1.....1.....1. ....1

1.....1.....1.....5.....1.....1.....1.....1.....1. ....1

1.....1.....1.....5.....1.....1.....1.....1.....1. ....1

1.....1.....A.....2.....1.....1.....B.....1.....1.....1

1.....1.....1.....1.....1.....1.....1.....1.....1. ....1

1.....1.....1.....1.....1.....1.....1.....1.....1. ....1

1.....1.....1.....1.....1.....1.....1.....1.....1. ....1

1.....1.....1.....1.....1.....1.....1.....1.....1. ....1

1.....1.....1.....1.....1.....1.....1.....1.....1. ....1

Position = x coordinate, y coordinate
A = 3 , 5
B = 7 , 5


Using separator " ^ " in the path represented by a string.


Using in a string form and placing that string in a vector array to be analyzed as I go and later.

 
/*
Beginning at 3,5 which is "A"
Move to     Total distance      Total moves     Represented by x and y      In string form      Using?
2,4         1                   1               3,5 to 2,4                  1 ^ 1 ^ 3,5to2,4    maybe, for some reference. So, save it to the array as a new entry to be analyzed later.
3,4         1                   1               3,5 to 3,4                  1 ^ 1 ^ 3,5to3,4    maybe, for some reference. So, save it to the array as a new entry to be analyzed later.
4,4         5                   1               3,5 to 4,4                  5 ^ 1 ^ 3,5to4,4    maybe, for some reference. So, save it to the array as a new entry to be analyzed later.
4,5         2                   1               3,5 to 4,5                  2 ^ 1 ^ 3,5to4,5    maybe, for some reference. So, save it to the array as a new entry to be analyzed later.
4,6         1                   1               3,5 to 4,6                  1 ^ 1 ^ 3,5to4,6    maybe, for some reference. So, save it to the array as a new entry to be analyzed later.
3,6         1                   1               3,5 to 3,6                  1 ^ 1 ^ 3,5to3,6    maybe, for some reference. So, save it to the array as a new entry to be analyzed later.
2,6         1                   1               3,5 to 2,6                  1 ^ 1 ^ 3,5to2,6    maybe, for some reference. So, save it to the array as a new entry to be analyzed later.
2,5         1                   1               3,5 to 2,5                  1 ^ 1 ^ 3,5to2,5    maybe, for some reference. So, save it to the array as a new entry to be analyzed later.
 
Beginning at 2,4
Move to     Total distance      Total moves     Represented by x and y              In string form                 Using?
1,3         2                   2               (3,5 to 2,4) then (2,4 to 1,3)      2 ^ 2 ^ 3,5to2,4 ^ 2,4to1,3    maybe, for some reference. So, save it to the array as a new entry to be analyzed later.
2,3         2                   2               (3,5 to 2,4) then (2,4 to 2,3)      2 ^ 2 ^ 3,5to2,4 ^ 2,4to2,3    maybe, for some reference. So, save it to the array as a new entry to be analyzed later.
3,3         2                   2               (3,5 to 2,4) then (2,4 to 3,3)      2 ^ 2 ^ 3,5to2,4 ^ 2,4to3,3    maybe, for some reference. So, save it to the array as a new entry to be analyzed later.
3,4         2                   2               (3,5 to 2,4) then (2,4 to 3,4)      2 ^ 2 ^ 3,5to2,4 ^ 2,4to3,4    NO since it is already being used in 3,5 to 3,4 and it has a shorter path of 1.
3,5         2                   2               (3,5 to 2,4) then (2,4 to 3,5)      2 ^ 2 ^ 3,5to2,4 ^ 2,4to3,5    NO since it is the origin 3,4 and it has a shorter path of 0.
2,5         2                   2               (3,5 to 2,4) then (2,4 to 2,5)      2 ^ 2 ^ 3,5to2,4 ^ 2,4to2,5    NO since it is already being used in 3,5 to 2,5 and it has a shorter path of 1.
1,5         2                   2               (3,5 to 2,4) then (2,4 to 1,5)      2 ^ 2 ^ 3,5to2,4 ^ 2,4to1,5    NO since it is already being used in 3,5 to 2,5 and it has a shorter path of 1.
 
Beginning at 3,4
Move to     Total distance      Total moves     Represented by x and y              In string form                Using?
... etc. 
 
*/
 
 

I want to put the results into a string array, a vector array consisting of strings.
I can sort through that later.


If I use this process, then I might have multiple variations of the shortest path to choose from.


If I could get this part to work, then I can place other conditionals (if needed) in also.

But, I am having difficulty with this part so far.

I can use a vector array of strings. But, this is more than I have been able to wrap my mind around and actually code in. I feel exasperated. Overwhelmed. etc.

Help please.