C++

Forum

 
Easiest Shortest Path C++ Program *Possibly*

MazharMustapha (34)
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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
 
/*This is a complete and correctly functioning 
  Shortest Path algorithm in C++ using Dijkstra's Algorithm.
  For information on how Dijkstra's Algorithm works:
  Visit the following link: https://www.youtube.com/watch?v=WN3Rb9wVYDY */
  /*This Program was designed and constructed by (Mazhar Mustapha)*/
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
using namespace std;

struct node { // Struct is for node or letter in the diagram, each node has a value attached to it according to Dijkstra's algorithm
	char symbol; 
	int v;
}; 
struct path { // Struct is for path of each edge. Each edge has a specific length
	string movement;
	int L;
};
void display(node *, int, path *, int, char, char); // Neatly display results of input
void test_path(char, char, path *, node *, int); // The actual process of testing and finding the shortest path
int find_path_sub(path *, char, int); // Find subscript for path location.
int find_path_sub_two(char); // Find subscript using last character in a string.
int find_path_sub_third(char); // Find subscript using first character in a string.
string find_path(char, node *, int); // Returns the deciphered string which had lowest path value.
int main()
{
	int x; char s, e;
	node *ptrN; path *ptrP;
	cout << "# of vertices: "; cin >> x; // Number of nodes
	const int n = x;
	ptrN = new node[n]; x = 97;
	for (int i = 0; i < n; i++)
	{
		ptrN[i].symbol = x; //Assigns a letter starting 'a' and increments to the defined number of n.
		x++;
	}
	cout << "Enter start and end: "; cin >> s >> e; // Start and Ending nodes, defined by its letter.
	for (int i = 0; i < n; i++)
	{
		if (s == ptrN[i].symbol)
			ptrN[i].v = 0; // Set starting node value to 0
		else
			ptrN[i].v = 9999999; // Set all other nodes to INFINITE.
	}
	cout << "Enter number of edges: "; cin >> x; // Number of connections
	const int m = x;
	ptrP = new path[m]; // Allocate number of paths needed.
	for (int i = 0; i < m; i++)
	{
		cin.ignore(20, '\n');
		cout << "[PATH] ";
		if (i == 0)
		{
			cout << "!ALPHABETICAL ORDER {EX. ab = (a to b)}"; // It is ESSENTIAL that the inputs here are entered in Alphebetical order, otherwise there will be errors.
		}
		cout << "| Edge " << (i + 1) << ": ";
		getline(cin, ptrP[i].movement);
		cout << "Length: "; cin >> ptrP[i].L;
	}
	display(ptrN, n, ptrP, m, s, e);
	test_path(s, e, ptrP, ptrN, m);
	delete[] ptrP;
	delete[] ptrN;
	system("PAUSE");
	return 0;
}
void display(node *PtrN, int n, path *PtrP, int m, char start, char end)
{
	cout << "Vertices: ";
	for (int i = 0; i < n; i++)
	{
		cout << PtrN[i].symbol << " ";
	}
	cout << endl << "Start: " << start << endl << "End: " << end << endl;
	cout << "-----PATHS-----\n";
	for (int i = 0; i < m; i++)
	{
		cout << PtrP[i].movement;
		cout << " - [L] = " << PtrP[i].L;
		cout << endl;
	}
}
void test_path(char start, char end, path *ptr, node *Ptr, int m)
{
	vector<int> record;
	vector<string> final;
	char begin = start; 
	int x, y, z, L;
	bool initial = true;
	string t, fpath;
	while (begin != end)
	{
		if(initial)
			x = find_path_sub(ptr, begin, m);
		initial = false;
		t = ptr[x].movement; // Set t with first path for while loop to activate.
		while (t[0] == begin && x < m)
		{
			y = find_path_sub_two(t[1]);
			z = find_path_sub_third(t[0]);
			Ptr[y].v = ptr[x].L + Ptr[z].v;
			record.push_back(Ptr[y].v);
			x++;
			if (x == m)
				continue;
			t = ptr[x].movement; // test while loop at the beginning.
		}
		if (record.size() != 0) {
			L = record[0];
			for (int i = 0; i < record.size(); i++)
			{
				if (record[i] < L)
					L = record[i];
			}
		}
		fpath = find_path(begin, Ptr, L);
		final.push_back(fpath);
		record.clear(); // Clear record for next loop.
		x = 0; // x equals 0 for safety purposes.
		initial = true; // Initial true for t to contain next path.
		begin = fpath[1]; // Begin ewuals the last character of the string. Example: a to b, now we need to start from b.
	}
	cout << "Final Path: ";
	for (int i = 0; i < final.size(); i++)
	{
		cout << final[i] << " ";
	}
	cout << endl;
}
int find_path_sub(path *ptr, char start, int size)
{
	string temp;
	for (int i = 0; i < size; i++)
	{
		temp = ptr[i].movement;
		if (start == temp[0])
			return i;
	}
}
int find_path_sub_two(char last)
{
	int j = 97;
	char test;
	for (int i = 0; ;i++)
	{
		test = j;
		if (test == last)
			return i;
		j++;
	}
}
int find_path_sub_third(char first)
{
	int j = 97;
	char test;
	for (int i = 0; ;i++)
	{
		test = j;
		if (test == first)
			return i;
		j++;
	}
}
string find_path(char b, node *ptr, int value)
{
	string f = "  ";
	f[0] = b;
	for (int i = 0; ;i++)
	{
		if (value == ptr[i].v)
		{
			f[1] = ptr[i].symbol;
			break;
		}
	}
	return f;
}


Probably the easiest shortest path program to understand and use.
Use the following links as an example:
https://upload.wikimedia.org/wikipedia/commons/thumb/3/3b/Shortest_path_with_direct_weights.svg/2000px-Shortest_path_with_direct_weights.svg.png

https://qph.is.quoracdn.net/main-qimg-d5e6840601c403b754a47ff1ae966de2?convert_to_webp=true

Designed by yours truly. Any thoughts or problems?

Example input: ALPHEBETICAL ORDER !
ab
ac
bc
bd
cd
de
Last edited on
cire (8284)
http://ideone.com/hjtye9 <- graph based off first pic linked above - doesn't work.

http://ideone.com/MLf6Xh <- graph based on second pick linked above - doesn't work.

Designed by yours truly. Any thoughts or problems?

Aside from the atrocious choice in variable names, it seems to... not work. I'm guessing, from the manual memory management and pointer ubiquity that this comes from undefined behavior as a result of accessing memory you have no business touching, but that's just a guess. I haven't looked at the code very hard.
MazharMustapha (34)
The input you put in is the problem. The values should all be lowercase.
I tested both of the graphs and the code works. In addition, the code safely accesses data.
Within the the test path function I have other functions to find subscripts, but for the record vector there is always at least ONE value in it, which is the reason for manual memory management.
MazharMustapha (34)
In addition, try using an actual environment like Visual Studio. Online compilers tend to be... eh..
MazharMustapha (34)
Graph of First Pic
https://upload.wikimedia.org/wikipedia/commons/thumb/3/3b/Shortest_path_with_direct_weights.svg/2000px-Shortest_path_with_direct_weights.svg.png

----------Output-------------

# of vertices: 6
Enter start and end: a f
Enter number of edges: 7
[PATH] !ALPHABETICAL ORDER {EX. ab = (a to b)}| Edge 1: ab
Length: 4
[PATH] | Edge 2: ac
Length: 2
[PATH] | Edge 3: bc
Length: 5
[PATH] | Edge 4: bd
Length: 10
[PATH] | Edge 5: ce
Length: 3
[PATH] | Edge 6: df
Length: 11
[PATH] | Edge 7: ed
Length: 4
Vertices: a b c d e f
Start: a
End: f
-----PATHS-----
ab - [L] = 4
ac - [L] = 2
bc - [L] = 5
bd - [L] = 10
ce - [L] = 3
df - [L] = 11
ed - [L] = 4
Final Path: ac ce ed df
Press any key to continue . . .
cire (8284)
In addition, try using an actual environment like Visual Studio. Online compilers tend to be... eh..

VS is actually the first thing I used. Barfed on a std::bad_alloc exception in test_path on line 97 with the variable x being a value that was inappropriate for indexing ptr.

I understand about online compilers. They tend to show flaws you haven't tested for in your original environment. eh...


The input you put in is the problem. The values should all be lowercase.
Upper or lower case makes no difference.

[Edit: Although, having gone through again with lower case, it seems to work. Perhaps I made a mistake entering data the first time. This code is awful fragile if that's all it takes to break.]
Last edited on
MazharMustapha (34)
Graph of Second Pic. Note: Paths go back and forth

https://qph.is.quoracdn.net/main-qimg-d5e6840601c403b754a47ff1ae966de2?convert_to_webp=true


-------------Output---------------

# of vertices: 4
Enter start and end: a b
Enter number of edges: 10
[PATH] !ALPHABETICAL ORDER {EX. ab = (a to b)}| Edge 1: ab
Length: 6
[PATH] | Edge 2: ac
Length: 3
[PATH] | Edge 3: ba
Length: 6
[PATH] | Edge 4: bc
Length: 4
[PATH] | Edge 5: bd
Length: 1
[PATH] | Edge 6: ca
Length: 3
[PATH] | Edge 7: cb
Length: 4
[PATH] | Edge 8: cd
Length: 1
[PATH] | Edge 9: db
Length: 1
[PATH] | Edge 10: dc
Length: 1
Vertices: a b c d
Start: a
End: b
-----PATHS-----
ab - [L] = 6
ac - [L] = 3
ba - [L] = 6
bc - [L] = 4
bd - [L] = 1
ca - [L] = 3
cb - [L] = 4
cd - [L] = 1
db - [L] = 1
dc - [L] = 1
Final Path: ac cd db
Press any key to continue . . .
MazharMustapha (34)
I don't understand that though. x is a valid subscript, the functions are correct. It is because you put uppercase values so it doesn't return anything, that's why. Maybe later I will use a 'toupper' for improvement. Try lowercase and see what happens.
MazharMustapha (34)
Lol it does. 'A' does not equal 'a'. I placed the example input with correct functioning example. Hope it's beneficial, let me know if it still has problems. I'm open to anything.
Last edited on
Topic archived. No new replies allowed.