C++

Forum

 
Adjaceny matrix for dijkstra shortest path algorithm

GillesCplusplus (9)
Hi guys, I want to apply dijkstra shortest path algorithm to the following 2 files:
projet14_milestone.txt
projet14_process.txt

projet14_milestone.txt looks like :
1
2
3
4
5
6
7
8
9
10
11
12
13
 
12
0,5,Start
1,1,A
4,1,B
7,1,C
2,2,D
1,3,E
2,4,F
6,2,G
7,3,H
5,4,I
7,4,J
4,3,End


12 is the number of stages I need to consider and is stored in the variable nb.
From then on , the first number respresents the x coordinate of a stage, the second number respresents the y coordinate of a stage and then we can see the name of the stage. So for example line 2 : The x-coordinate of stage 'start' is 0 and is stored in milestone_x, the y coordinate of the stage 'start' is 5 and is stored in milestone_y. the name of the stage is stored in milestone_nom.




projet14_process.txt looks like : 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 

PROCESS1,-3.88,Start,A
PROCESS2,-5.2,Start,B
PROCESS3,-7.97,Start,C
PROCESS4,-0.43,A,D
PROCESS5,-2.2,B,D
PROCESS6,-1.2,C,G
PROCESS7,-3.18,D,G
PROCESS8,-0.42,E,D
PROCESS9,-0.69,H,G
PROCESS10,-0.94,H,J
PROCESS11,-1.64,H,I
PROCESS12,-1.49,J,I
PROCESS13,-2.4,I,F
PROCESS14,-0.58,E,F
PROCESS15,-1.22,End,I
PROCESS16,-1.24,End,F

There are 16 different processes and each process consumes a certain amount of paint. Each process is defined by 2 stages. For example process 1 consumes -3,88 units of paint and connects stage 'start' with A. As it is and undirected graph, D->G consumes the same amount as G->D.

Thus far, I've written a code to become the adjacency matrix. The first row represents start, the second A, and so on. The first column represents start, the second A, and so on. As process 1 connects start with A, adjmatrix [0][1]= -3,88 and adjmatrix [1][0]= -3,88

But this code cannot attach the value -3,88 to this step, can someone help me?

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
 
#include <iostream>
#include <fstream>
#include <cstring> 
#include <string>
using namespace std;



class Algorithme {

	private:
		int i= 0;

		struct milestone
				{
					int milestone_x;
					int milestone_y;
					char milestone_nom[6];
				};

		int nb = 12;
		milestone node[12];


		struct process
			{
			  char process_nom[20];
			  float process_consomation;
			  char process_node1[6];
			  char process_node2[6];
						};
		process procedure[16];


	public:

		void lecture();
		void adjmatr();


};





void Algorithme::lecture() {
// lecture document 1


	string ligne;

	ifstream infile;
	infile.open("/Users/gillescorswarem/documents/projet14_milestone.txt"); 

	if (infile.fail()) {
		cout << "erreur de lecture: document: milestone\n";
	}


		infile >> nb; 


	for ( i=0; i < nb;i++) {

		getline(infile,ligne,',');
				node[i].milestone_x = std::atoi(ligne.c_str());

		getline(infile,ligne,',');
					node[i].milestone_y = std::atoi(ligne.c_str());
		getline(infile,ligne);
				   strcpy(node[i].milestone_nom, ligne.c_str()); 
		}


	infile.close();



	string ligne2;
	ifstream infile2;
	infile2.open("/Users/gillescorswarem/documents/projet14_process.txt"); 
	if (infile2.fail())
		cout << "erreur de lecture: document: process\n";



	for ( i=0; i < 16;i++) {

	   getline(infile2,ligne2,',');
					strcpy(procedure[i].process_nom, ligne2.c_str()); 

		getline(infile2,ligne2,',');
					procedure[i].process_consomation = std::atof(ligne2.c_str()); 

		getline(infile2,ligne2,',');
					strcpy(procedure[i].process_node1, ligne2.c_str());

		getline(infile2,ligne2);
					strcpy(procedure[i].process_node2, ligne2.c_str()); 


		}
	infile2.close();

		
}

void Algorithme::adjmatr() {
	float adjmatrix [12][12];
	for (int a=0; a<16; a++){
		for (int b=0; b<12; b++){
			if (strcmp(procedure[a].process_node1,node[b].milestone_nom) == 0) {
					for (int c=0;c<12;c++){
							if ( strcmp (procedure[a].process_node2,node[c].milestone_nom) == 0)	{
								adjmatrix[b][c]= procedure[a].process_consomation;
								adjmatrix[c][b]= procedure[a].process_consomation;
							}

					}
		}
	}
	}


	cout << adjmatrix [0][1] << endl;
	cout << adjmatrix [4][7] << endl;



}


int main() {
	Algorithme reponse;
	reponse.lecture();
	reponse.adjmatr();
	return 0;
}





ne555 (10692)
this is the matrix read 
##### -3.88 -5.20 -7.97 ##### ##### ##### ##### ##### ##### ##### ##### 
-3.88 ##### ##### ##### -0.43 ##### ##### ##### ##### ##### ##### ##### 
-5.20 ##### ##### ##### -2.20 ##### ##### ##### ##### ##### ##### ##### 
-7.97 ##### ##### ##### ##### ##### ##### -1.20 ##### ##### ##### ##### 
##### -0.43 -2.20 ##### ##### -0.42 ##### -3.18 ##### ##### ##### ##### 
##### ##### ##### ##### -0.42 ##### -0.58 ##### ##### ##### ##### ##### 
##### ##### ##### ##### ##### -0.58 ##### ##### ##### -2.40 ##### -1.24 
##### ##### ##### -1.20 -3.18 ##### ##### ##### -0.69 ##### ##### ##### 
##### ##### ##### ##### ##### ##### ##### -0.69 ##### -1.64 -0.94 ##### 
##### ##### ##### ##### ##### ##### -2.40 ##### -1.64 ##### -1.49 -1.22 
##### ##### ##### ##### ##### ##### ##### ##### -0.94 -1.49 ##### ##### 
##### ##### ##### ##### ##### ##### -1.24 ##### ##### -1.22 ##### #####
(##### means no value) ¿is that correct? ¿do you get something different?

you should initialise all the elements of `adjmatrix' to an "infinite" value or you'll end up with extra edges.
GillesCplusplus (9)
This is indeed the matrix I have to become!
I want to replace all the ##### by the value 0 or infinity. 0 is also possible I believe, because I am working with negative values

But when I run the program and try to print adjmatrix [0][1] and adjmatrix [4][7] I always get the value 0.
1
2
3
 
cout << adjmatrix [0][1] << endl;
cout << adjmatrix [4][7] << endl;


According to the matrix, adjmatrix [0][1] has to be equal to -3,88 and adjmatrix [4][7] to -3,18. Why does the program print 0 each time?
Last edited on
ne555 (10692)
I don't see any particular wrong in your code, and it does work in my end.
initialise `adjmatrix' and print it fully

may use a debugger to see if you do reach line 116 and to inspect the `procedure' and `node' arrays after reading from the files.
Topic archived. No new replies allowed.