djikstra shortest path

#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 1000
#define infin 65555
int parent[maxn + 1] = { -1 };
struct edgenode
{
	int y;
	int weight;
	edgenode* next;
};
struct graph
{
	edgenode* edges[maxn + 1];
	int degree[maxn + 1];
	int nvertices;
	int nedges;
	bool directed;
};
void init_graph(graph* G, bool directed)
{
	int i;
	G->nvertices = 0;
	G->nedges = 0;
	G->directed = directed;
	for (i = 1; i <= maxn; i++)
	{
		G->degree[i] = 0;
	}
	for (i = 1; i < maxn; i++)
	{
		G->edges[i] = NULL;
	}
}
void insert_edge(graph* G, int x, int y, int weight, bool directed)
{
	edgenode* p;
	p = new edgenode;
	p->weight = weight;
	p->y = y;
	p->next = G->edges[x];

	G->edges[x] = p;
	G->degree[x]++;
	if (directed == false)
	{
		insert_edge(G, y, x, weight, true);
	}
	else
	{
		G->nedges++;
	}
 }

void read_graph(graph* G, bool directed)
{
	int i, m;
	int x, y;
	int weight;
	init_graph(G, directed);
	cout << "点的数量:";
	cin >> G->nvertices;
	cout << "边的数量:";
	cin >> m;
	for (i = 1; i <= m; i++)
	{
		cout << "从此点出发:";
		cin >> x;
		cout << "到此点:";
		cin >> y;
		cout << "输入边的权重:";
		cin >> weight;
		insert_edge(G, x, y, weight, directed);
	}
}

void print_graph(graph* G)
{
	int i;
	edgenode* p;
	cout << "Vertex\tConnected" << endl;
	for (i = 1; i < G->nvertices; i++)
	{
		cout << i << "\t";
		p = G->edges[i];
		while (p != NULL)
		{
			cout << i << "\t";
			p = p->next;
		}
		cout << endl;
	}
}

void find_path(int start, int end, int parents[])
{
	if ((start == end) || (end == -1))
	{
		cout << endl << start;
	}
	else
	{
		find_path(start, parents[end], parents);
		cout << " " << end;
	}
}

void djikstra(graph* G, int start)
{
	int i;
	edgenode* p;
	bool intree[maxn + 1];
	int distance[maxn + 1];
	int v, w;
	int weight;
	int dist;
	for (i = 1; i <= G->nvertices; i++)
	{
		intree[i] = false;
		distance[i] = infin;
		parent[i] = -1;
	}
	distance[start] = 0;
	v = start;
	while (intree[v] == false)
	{
		intree[v] = true;
		p = G->edges[v];
		while (p != NULL)
		{
			w = p->y;
			weight = p->weight;
			if (distance[w] > distance[v] + weight)
			{
				distance[w] = distance[v] + weight;
				parent[w] = v;
			}
			p = p->next;
		}
		v = 1;
		dist = infin;
		for (i = 1; i <= G->nvertices; i++)
		{
			if ((intree[i] == false) && (dist > distance[i]))
			{
				dist = distance[i];
				v = i;
			}
		}
	}
}

int main()
{
	graph G;
	int start;
	int end;
	read_graph(&G, 0);
	print_graph(&G);
	cout << "输入起点 :";
	cin >> start;
	cout << "输入终点 :";
	cin >> end;
	djikstra(&G, start);
	if (parent[end] == -1 && start != end)
	{
		cout << "路径不存在";
	}
	else
	{
		cout << "路径从 " << start << "到" << end << "如下: ";
		find_path(start, end, parent);
	}
	return 0;
}