数据结构第七节(图(中))
图(中)
在上一节的时候曾说过了图的两种遍历方式，在这一节将使用他们做更深层的应用，研究从一个点到另一个点的最短距离。
最短路径问题
单源无权图的最短路径
基本思想是，按照非递减的顺序，找出各个点的最短路。
很容易想到按照非递减的顺序，也就是优先从原点开始，不断的计算与他相距最近的点的距离，整个的过程就是一个BFS。
在bfs的过程中，我们之前是用一个布尔类型的数组来保存一个节点是否被访问。现在我们可以将其改成为int类型的二维数组，同时该数组还需要实现两个功能，对于第I个节点Vertex i，p[ i ][ 0 ]用于保存它到原点的距离，而p[ i ][ 1 ]用于保存最短路径中他被哪个节点所指。在输出最短路径时，我们只需要沿着它的路径倒着走直到原点，反一下就是正确的路径了。
//无全权图最短路径
int p[MAXSIZE][2];
void UnweightShortestPath(Graph G, Vertex x) {
for (int i = 0; i < MAXSIZE; i++)
{
memset(p[i], -1, sizeof(p[i]));
}
//自己到自己的距离是0
p[x][0] = 0;
Queue Q = makeempty();
QueueAdd(x, Q);
while (!isEmpty(Q))
{
Vertex v = QueueDelete(Q);
for (int i = 0; i < G->Nvertex; i++)
{
if (G->graph[v][i] != 0 && p[i][0]==-1) {
p[i][0] = p[v][0] + 1;
p[i][1] = v;
QueueAdd(i, Q);
}
}
}
int end;
scanf_s("%d", &end);
stack<int> v;
}
单源有权图的最短路径(Dijkstra算法)
Dijkstra算法的基本算法思想是：创建一个集合S，不断的向该集合中添加顶点，每次移出时确定了该顶点的最短的。随着不断的添加，移除使得所有顶点的最短路径都被确定为最小。(贪心算法的思想)
具体实现是首先从原点开始，将其标记为已读(代表该点在整个图中最短路径确定 )，将它的所有连接点加入集合中，并将这些点到原点的最短距离设置为权值，并标记他们指向原点(在确定了最短路径打印时需要用)。
随后从集合中移除距离最小的一个，将该节点标记为已读(该点最短路径一定已经确定，因为他是原点的连接点中距离最短的那个，如果从原点经过其他的节点到他，距离必定会更大)。
将该节点的邻接点加入集合，并将这些点到原点的最短距离设置为移除点的最短距离加上自身到移除点的距离和自己原来最短距离中的最小值。
即\(dp[ i ] = Min\){\(dp[ i ] ,dp[ v ]+weight[ v ][ i ]\)}(\(dp[ i ]\)表示i点到远点的最短距离\(weight[ v ][ i ]\)v到i的距离)。
递归的则运行直到所有的点都被集合收入又移出结束。
注意到：在上面的算法中我们是不断的距离从近到远，在图中如果有负值出现的话，我们将会在这个负值圈内打转。该算法再存在负值的权值是无效的。
#define INFINITY 10000000
//不同的编辑器该值并不相同，可能会报导致值为0
//find MinDis
Vertex findMin(Graph G,int dis[],bool collection[]) {
Vertex minV = 0;
int minDis = INFINITY;
for (Vertex i = 0; i < G->Nvertex; i++)
{
if (collection[i] == false && dis[i] < minDis) {
minDis = dis[i];
minV = i;
}
}
//如果最短距离被改变,说明有找到
if (minDis < INFINITY) {
return minV;
}
return notFound;
}
//Dijkstra
//注意，在该有权值图中，应是无边连接的两点为正无穷大
bool Dijkstra(Graph G, Vertex x) {
//save information
int shortDis[MAXSIZE];
bool collection[MAXSIZE];
int path[MAXSIZE];
memset(shortDis, INFINITY, sizeof(shortDis));
memset(collection, false, sizeof(collection));
memset(path, -1, sizeof(path));
//先将起始点的连接点距离初始化
for (Vertex i = 0; i <= G->Nvertex; i++)
{
shortDis[i] = G->graph[x][i];
if (shortDis[i] < INFINITY) {
path[i] = x;
}
}
collection[x] = true;
shortDis[x] = 0;
while (true)
{
Vertex v = findMin(G, shortDis, collection);
if (v == notFound) {
break;
}
collection[v] = true;
for (Vertex i = 0; i <= G->Nvertex; i++)
{
if (G->graph[v][i] < INFINITY && collection[i] == false) {
//存在负值圈算法无法正常进行
if (G->graph[v][i] < 0) {
return false;
}
/*
* 移除点的最短距离加上自身到移除点的距离小于自己原来最短距离。
*/
if (shortDis[i] > shortDis[v] + G->graph[v][i]) {
shortDis[i] = shortDis[v] + G->graph[v][i];
path[i] = v;
}
}
}
}
return true;
}
多源有权图的最短路径(Floyd算法)
在上面的方法中为了求某一点到与固定点的最短距离，使用Dijkstra算法，现在我们要求任意两点间的最短距离，我们当然可以将所有的点都用一次Dijkstra算法来得到，以后更简单更快的方法是使用Floyd算法。
Floyd算法的算法思路是：
用一个二维数组dp[ ][ ]来保存第I个点到第J这个点的最短距离。
每次循环尝试在I到J的路径中，加入第K个节点(k = 1…..N)试试会不会让路径变短，如果路径会变短即(\(dp[ i ][ j ]<dp[ i ][ k ]+dp[ k ][ j ]\))，就更新\(dp[ i ][ j ]=dp[ i ][ k ]+dp[ k ][ j ]\)，否则不变。经过K轮循环之后，我们将会得到所有的任意两点间的最短路径同样的 。
该算法如何进行：
初始的时候我们令数组保存的是原来图中两点的距离，并且将自己指向自己的距离设为1。在插入第1个节点时(在程序中下标为0)，我们注意到在起始点或结束点有该第一个节点的话，是不会改变的，即\(dp[ i ][ 0 ]==dp[ i ][ 0 ]+dp[ 0 ][ 0 ]\)或\(dp[ 0 ][ j ]==dp[ 0 ][ 0 ]+dp[ 0 ][ j ]\)，注意到\(dp[ i ][ j ] = Min(dp[ i ][ 0 ]+dp[ 0 ][ j ],dp[ i ][ j ])\)。循环着往下走我们发现，每次\(dp[ i ][ j ]\)的值改变，一定是由第K行和第K列决定，而该列在此轮外循环中，值绝对不会发生改变。
同上面的算法一样该算法在存在负值圈的时候，也会出问题。
bool Floyd(Graph G) {
int dp[MAXSIZE][MAXSIZE];
int path[MAXSIZE][MAXSIZE];
for (int i = 0; i <= G->Nvertex; i++)
{
for (int j = 0; j <= G->Nvertex; j++)
{
if (i == j) {
dp[i][j] = 0;
}
else {
dp[i][j] = G->graph[i][j];
}
}
}
for (int i = 0; i <= G->Nvertex; i++)
{
for (int j = 0; j <= G->Nvertex; j++)
{
for (int k = 0; k <= G->Nvertex; k++)
{
if (dp[i][j] > dp[i][k] + dp[k][j]) {
dp[i][j] = dp[i][k] + dp[k][j];
if (i == j && dp[i][j] < 0) {
return false;
}
path[i][j] = k;
}
}
}
}
return true;
}
