0

Hi. I need to write a program that finds the shortest route in directed graph.

Please look at the picture.

Click Here

Here is my code:

```
#include <iostream>
using namespace std;
const int N = 10;
struct elem
{
char key;
elem *next;
} *g[N];
void init(elem *g[N])
{
for (int i = 0; i < N; i++)
g[i] = NULL;
}
int search_node(char c, elem *g[N])
{
for (int i = 0; i < N; i++)
if (g[i])
if (g[i]->key == c)
return 1;
return 0;
}
int search_arc(char from, char to, elem *g[N])
{
if (search_node(from, g) && search_node(to, g))
{
int i = 0;
while (g[i] == NULL || g[i]->key != from) i++;
elem *p = g[i];
while(p->key != to && p->next)
if (p->key == to)
return 1;
}
return 0;
}
void add_node(char c, elem *g[N])
{
if (search_node(c, g))
cout << "Node already exists.\n";
int i = 0;
while (g[i] && (i < N)) i++;
if (g[i] == NULL)
{
g[i] = new elem;
g[i]->key = c;
g[i]->next = NULL;
}
else
{
cout << "Maximum nodes reached.\n";
}
}
void add_arc(char from, char to, elem *g[N])
{
if (search_arc(from, to, g))
cout << "Arc already exists.\n";
else
{
if (!search_node(from, g))
add_node(from, g);
if (!search_node(to, g))
add_node(to, g);
int i = 0;
while (g[i] == NULL || g[i]->key != from) i++;
elem *p = new elem;
p->key = to;
p->next = g[i]->next;
g[i]->next = p;
}
}
void del_node(char c, elem *g[N])
{
if(search_node(c, g))
{
int i = 0;
while(g[i] == NULL || g[i]->key != c)
i++;
elem *p, *q;
while(g[i])
{
p = g[i];
g[i] = g[i]->next;
delete p;
}
for(int i = 0; i < N; i++)
if(g[i])
{
p = g[i];
while(p->key != c && p->next)
{
q = p;
p = p->next;
}
if(p->key == c)
{
q->next = p->next;
delete p;
}
}
}
else
cout << "\nThe node is not in the graph!" << endl;
}
void del_arc(char c1, char c2, elem *g[N])
{
/*if(search_arc(c1, c2, g))
{
int i = 0;
while(g[i])
}*/
}
int cnt = 0;
void print(elem *g[N])
{
for (int i = 0; i < N; i++)
if (g[i])
{
elem *p = g[i];
while(p)
{
cout << p->key << "\t";
p = p->next;
cnt++;
}
cout << endl;
}
cout << "Number of nodes: " << cnt << endl;
}
/*
void dijkstra()
{
int s[N] = {0}; // N - number of nodes in graph
int d[N]; // array, which store the shortest paths from the start
int p[N]; // p is supporting array containing peaks prior to the current special path
int w, i;
s[0] = 1;
int c[N];
for(int i = 1; i < N; i++)
{
d[i] = c[0, i];
p[i] = 0;
}
for(int i = 1; i < N; i++)
{
s[w] = 1;
for(int i = 1; i < N; i++)
if(s[i] == 0)
if(d[i] > d[w] + c[w, i])
{
p[i] = w;
d[i] = d[w] + c[w, i];
}
}
}
*/
int main()
{
int choice;
do
{
cout<<"\n\t\t\t\t MAIN MENU\n";
cout<<"\t\t # # # # # # # # # # # # # # # # # # # # #"<<endl;
cout<<"\t\t # #";
cout<<"\n\t\t # 1. Search node #";
cout<<"\n\t\t # 2. Search add #";
cout<<"\n\t\t # 3. Add node #";
cout<<"\n\t\t # 4. Add arc #";
cout<<"\n\t\t # 5. Pring graph #";
cout<<"\n\t\t # 6. Find shortest cycle #";
cout<<"\n\t\t # 7. Delete node #";
cout<<"\n\t\t # 8. Delete arc #";
cout<<"\n\t\t # 9. Exit #"<<endl;
cout<<"\t\t # #";
cout<<"\n\t\t # # # # # # # # # # # # # # # # # # # # #"<<endl;
cout<<"\n\t\t Select your choice: ";
cin >> choice;
cout<<"\n";
char node_key;
char from, to;
switch(choice)
{
case 1:
cout << "Node key: ";
cin >> node_key;
cout << (search_node(node_key, g) ? "Node exists." : "Node doesn't exist." ) << endl;
break;
case 2:
cout << "From: ";
cin >> from;
cout << "To: ";
cin >> to;
cout << (search_arc(from, to, g) ? "Arc exists." : "Arc doesn't exist." ) << endl;
break;
case 3:
cout << "Node key: ";
cin >> node_key;
add_node(node_key, g);
break;
case 4:
cout << "From: ";
cin >> from;
cout << "To: ";
cin >> to;
add_arc(from, to, g);
break;
case 5:
print(g);
break;
case 6:
dijkstra();
break;
case 7:
break;
case 8:
break;
case 9:
exit(0);
break;
}
} while (true);
system("pause");
return 0;
}
```

I try to use the algorithm of Dijkstra, but something is not working.