【图】最短路径算法

#include<iostream>
#include<queue>
using namespace std;

/*
	邻接列表的大致排列类似于哈希表
	自己定义出"邻接桶"的概念，类似于“哈希桶”
	邻接桶中存着每个顶点
	每个顶点的通过EdgeNode——边，来链接着顶点和顶点，
	每个顶点都可以作为起始点，指向/被指向。


	这个容器就是“邻接桶”
						   *
	*			*			*
	*			**************	
	*			*			*
	*			*		   *
	*			*	
	*			*	
	*			*	
	*			*		   *
	*			*			*
	*			**************	
	*			*			*
	*			*		   *	
	*			*	
	*			*	
	*			*	
	*			*	
	*			*		   *
	*			*			*
	*			**************	
	*			*			*
	*			*		   *
	*			*	
	*			*	
	*			*	
	*	顶点	*	
	*			*	
	*			*	
	************
*/
#define Max_Size 1024 
bool visited[Max_Size];
typedef struct _EdgeNode
{
	int adjvex;
	int weight;
	struct _EdgeNode* next;
}EdgeNode;

typedef struct _VertexNode//顶点结点，这个就是邻接桶
{
	char data;//结点数据
	struct _EdgeNode* first;//指向邻接第一条边
}VertexNode, AdjList;

typedef struct _AdjListGraph
{
	AdjList* adjlist;
	int vex;//顶点数
	int edge;//边数

}AdjListGraph;

//通过顶点对应的字符来寻找顶点在图中的邻接点
int Location(AdjListGraph& G,char c)
{
	for (int i = 0; i < G.vex; i++)
	{
		if (G.adjlist[i].data == c)
		{
			return i;
		}
	}
	return -1;
}

//图的初始化
void initGraph(AdjListGraph& G)
{
	G.adjlist = new AdjList[Max_Size];//左侧的邻接桶
	G.edge = 0;
	G.vex = 0;
	
	for (int i = 0; i < Max_Size; i++)
	{
		visited[i] = false;	
	}
}

//图的创建
void createGraph(AdjListGraph& G)
{
	cout << "请输入该图的顶点数以及边数" << endl;
	cin >> G.vex >> G.edge;
	cout << "请输入顶点data" << endl;
	for (int i = 0; i < G.vex; i++)
	{
		cin >> G.adjlist[i].data;//输入顶点所存数据
		G.adjlist[i].first = NULL;//边和边的关系，置空，先不与任何边相连。
	}	


	//确定顶点与顶点之间的关系，两个顶点形成一条边，有几条边，就有几对i1 i2

	char v1 = 0, v2 = 0;//保存输入的顶点的字符
	int i1 = 0, i2 = 0;//保存顶点在数组中的下标
	//将i1和i2链接起来
	//i1为起点。i2为终点。

	//保存边的权重
	int weight = 0;

	cout << "请输入想关联边的顶点" << endl;
	for (int i = 0; i < G.edge; i++)
	{
		cin >> v1 >> v2 >> weight;//以v1为起点，v2为终点的边，权重是weight
		i1 = Location(G, v1);
		i2 = Location(G, v2);
		//说明存在
		if (i1 != -1 && i2 != -1)
		{
			EdgeNode* temp = new EdgeNode;
			temp->adjvex = i2;
			temp->next = G.adjlist[i1].first;//头插法-类似于hashtable中的插入数据
			temp->weight = weight;
			G.adjlist[i1].first = temp;
		}
	}
}

//图的最短路径算法

int min_weight = 0x7FFFFFFF;//定义一个最大的方便与之比较。（INT_MAX）
int steps = 0;//已走过的步数
int path[Max_Size ] = { 0 };//保存走过的路径
int shortest_path[Max_Size] = { 0 };//保存最短路径

//求图的最短路径——深度优先遍历（前提是连通图）
//                            起点   终点      已走过的权重和   
void DFS(AdjListGraph& G,int start ,int end,int weights)
{
	int cur = -1;

	if (start == end)//已经找到终点了，不需要遍历了
	{
		for (int i = 0; i < steps; i++)
		{
			cout << G.adjlist[path[i]].data << " ";//path中存的是对应结点在邻接桶中的下标，通过这个下标就能找到对应的data,即可找到走过的路径
		}	
		cout << "该路径对应的长度是:" << weights << endl;//输入对应的路径长度

		if (min_weight > weights)//取到当前最小路径
		{
			min_weight = weights;
			memcpy(shortest_path, path, steps * sizeof(int));
		}
		return;
	}
	visited[start] = 1;
	EdgeNode* temp = G.adjlist[start].first;//指向第一条边

	while (temp)
	{
		int weight = temp->weight;
		cur = temp->adjvex;//通过这条边的指向，指过来的这个顶点，在邻接桶中的下标
		if (!visited[cur])
		{
			visited[cur] = 1;//标记已经访问
			path[steps++] = cur;
			//递归
			DFS(G, cur, end, weights+weight);

			visited[cur] = 0;//前一步探索完成后，置空cur,（应该是有路线含有重复结点时起到作用）
			path[--steps] = 0;//路径回退
		}
		temp = temp->next;
	}
}

int main(void)
{
	AdjListGraph G;
	//初始化
	initGraph(G);
	//创建图
	createGraph(G);
	//深度优先-寻找最短路径
	DFS(G, Location(G, 'A'), Location(G, 'D'), 0);
	cout << "成功得到最短路径为" << endl;
	//最短路径
	int i = 0;
	cout << "起点";
	while (shortest_path[i] > 0 && i < Max_Size)
	{
		cout << "->" << G.adjlist[shortest_path[i]].data ;
		i++;
	}
	cout << endl;
	return 0;

}