图的最短算法
从起点开始访问所有路径，可以到达终点的有多条地址,其中路径权值最小的为最短路径。
最短路径算法有深度优先遍历、广度优先遍历、Bellman-Ford算法、弗洛伊德算法、SPFA(Shortest Path Faster Algorithm)算法和迪杰斯特拉算法等。
本代码使用深度优先遍历
主要实现思路：
从起点开始，到达终点有多条分支，这些分支中又有多条分支...
选择其实一条分支，走到终点，再选择另一个分支(temp = temp ->next)走到终点，分支的分支......
大致流程:
代码实现:
#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;
}
输入示例：
