[图算法]Floyd算法改进之打印路径.
[图算法]Floyd算法改进之打印路径.
Floyd算法虽然形式上简单,但功能强大,除了可以求出图中任意两点间的最短路径外
(参: http://blog.csdn.net/EmilMatthew/archive/2005/08/10/450051.aspx)
还能再稍加修改的情况下,通过一个信息矩阵来得出任意两点间最短路径的中结点的信息.
具体的算法如下:
Step1:
1) 准备原带权矩阵wArr及结点信息矩阵wAns.wAns中的元素wAns[i][j]表示的是从结点i到结点j的最短路径中，位于结点j前的那个结点;在原图权值矩阵wArr中,如果两个结点这之前在起始图中没有直接相连的路径，则用一个大整数表示它们间的权值.
2) For i<-1 to len
3) For j<-1 to len
4) If mapArr[i][j]<IntLimit then
5) ansArr[i][j]=i;//如果原图中两个结点I,j连通，则在j结点前的最近结点为i
6) End if
7) Next j
8) Next i
Step2:
1) 在Floy最短路径算法中加入对结点信息矩阵wAns相关的处理信信息，其实就多加了一句.
2) For k<-0 to len
3) For i<-0 to len
4) For j<-0 to len
5) newLen<-mapAr)[i][k]+mapArr[k][j]
6) If (newLen<mapArr[i][j]) then
7) mapArr[i][j]<-newLen;
8) ansArr[i][j]<-ansArr[k][j];//在找到最短路径后,更新结点信息矩阵wAns，使ansArr[i][j]始终表示的是从结点i到结点j的最短路径中，位于结点j前的那个结点
9) End if
10) Next j
11) Next i
12) Next k
至此，伴随着Floyd算法进行，最短路径的结点信息矩阵wAns构造也完成了.
Step2:
ansArr中内容的读取
由于ansArr[i][j]表示的是从结点i到结点j的最短路径中，位于结点j前的那个结点,所以，如果要获得由I到j的最短路径上的各个结点的信息，可以通过从j一直寻访到I的方式来做，将果存放在一个栈中，最后，将栈中内容弹出，即得由I到j的最短
路径上各结点的信息.
具体的算法如下:
1) 给出初结点startNodeId和终止结点endNodeId
2) 初始结点压栈myStack.push(endNodeId)
3) 得到中介结点midNode=wAns[startNodeId][endNodeId]
4) 中介点压栈myStack.push(midNode);
5) while(midNode!=startNodeId)
//如果中介点不是起始点，则进入循环，直到找起始点为止.
{
6) midNode=wAns[startNodeId][midNode];
7) myStack.push(midNode);
}
8) while(!myStack.isEmpty())//输出栈中的信息，即得最路径上各结点的信息.
9) print myStack.pop()
算法结束.
下面给出本算法的实现,在这里，除了输出两个结点的信息外，还输了图中所有结点间最短路径的信息.
/*The floyd2 algorithm ,with could trace out the shortest path node’s information
Made by EmilMatthew 05/8/13*/
/*A very simple stack */
#include <stdlib.h>
#ifndef SIMPLESTACK_H
#define SIMPLESTACK_H
#define StackDataType long
class SimpleStack
{
public:
SimpleStack()
{
mLen=100;
mData=new StackDataType[mLen];
nextSlot=0;
}
SimpleStack(int len)
{
mLen=len;
mData=new StackDataType[mLen];
nextSlot=0;
}
~SimpleStack()
{
mLen=100;
delete []mData;
nextSlot=0;
}
void deleteAllValues()
{
delete []mData;
nextSlot=0;
}
void push(StackDataType inVal);
StackDataType pop();
StackDataType top();
bool isEmpty()
{
return nextSlot==0;
}
private:
StackDataType* mData;
int mLen;
int nextSlot;
};
#endif
/*SimpleStack.cpp*/
#include "SimpleStack.h"
#include "MyAssert.h"
#include <stdio.h>
void SimpleStack::push(StackDataType inVal)
{
/*to enlarge the capacity of the arr*/
if(nextSlot>=mLen)
{
int i=0;
StackDataType* tmpArr;
/*memroy apply*/
tmpArr=new StackDataType[nextSlot];
assertF(tmpArr!=NULL,"in StackDataType SimpleStack::pop tmpArr is NULL\n");
/*copy from mData to tmpArr*/
for(i=0;i<nextSlot;i++)
tmpArr[i]=mData[i];
/*free the space before apply new space*/
delete []mData;
mLen+=100;/*stack length be bigger*/
mData=new StackDataType[mLen];/*memory apply*/
for(i=0;i<nextSlot;i++)
mData[i]=tmpArr[i];
delete []tmpArr;/*free the space of the tmp pointer*/
}
mData[nextSlot++]=inVal;
}
StackDataType SimpleStack::pop()
{
assertF(!isEmpty(),"in StackDataType SimpleStack::pop the stack is Empty.\n");
return mData[--nextSlot];
}
StackDataType SimpleStack::top()
{
assertF(!isEmpty(),"in StackDataType SimpleStack::top the stack is Empty.\n");
return mData[nextSlot-1];
}
#include "SimpleStack.h"
#include "MyAssert.h"
#include "Global.h"
#include "Ulti.h"
#include "GraphAlgorithm.h"
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
char *inFileName="inputData.txt";
/*
input data specification
row,col
wArr
{
, , , ,
, , , ,
, , , ,
}
*/
char *outFileName="outputData.txt";
#define DEBUG 1
void main(int argc,char* argv[])
{
FILE *inputFile;/*input file*/
FILE *outputFile;/*output file*/
double startTime,endTime,tweenTime;/*time callopsed info*/
int row,col;
int startNodeId=0,endNodeId=0;
int i,j;/*iterator index*/
int n;/*arr deminision for squre matrix*/
SimpleStack myStack;
Type** wArr;
Type** wAns;
Type midNode;
/*input file open*/
if(argc>1)strcpy(inFileName,argv[1]);
assertF((inputFile=fopen(inFileName,"rb"))!=NULL,"input file error");
printf("input file open success\n");
/*outpout file open*/
if(argc>2)strcpy(outFileName,argv[2]);
assertF((outputFile=fopen(outFileName,"wb"))!=NULL,"output file error");
printf("output file open success\n");
fscanf(inputFile,"%d,%d,",&row,&col);
/*Memory apply*/
wArr=(Type**)malloc(sizeof(Type*)*row);
for(i=0;i<row;i++)
wArr[i]=(Type*)malloc(sizeof(Type)*col);
wAns=(Type**)malloc(sizeof(Type*)*row);
for(i=0;i<row;i++)
wAns[i]=(Type*)malloc(sizeof(Type)*col);
/*Read 2d arr data*/
for(i=0;i<row;i++)
{
for(j=0;j<col-1;j++)
fscanf(inputFile,"%d,",&wArr[i][j]);
fscanf(inputFile,"%d;",&wArr[i][j]);
}
/*big length adjust*/
for(i=0;i<row;i++)
for(j=0;j<col;j++)
if(wArr[i][j]==-1)wArr[i][j]=IntLimit;
show2DArrInt(wArr,row,col);
fscanf(inputFile,"%d,%d,",&startNodeId,&endNodeId);
printf("start:%d,end:%d.",startNodeId,endNodeId);
#if DEBUG
printf("\n*******start of test program******\n");
printf("now is runnig,please wait...\n");
startTime=(double)clock()/(double)CLOCKS_PER_SEC;
/******************Core program code*************/
/*argu prepare*/
assertF(col==row,"in test col!=row");
n=row;/*get the size of square matrix*/
Floyd2(&wArr,&wAns,n);
fprintf(outputFile,"===Output the node info matrix.===\r\n");
output2DArrInt(wAns,row,col,outputFile);
fprintf(outputFile,"===End of output the node info matrix.===\r\n");
assertF(startNodeId>=0&&endNodeId>=0&&startNodeId<n&&endNodeId<n,"in test,start and end id is illegal\n");
/*Trace out the shortest path from startNode to endNode*/
myStack.push(endNodeId);
midNode=wAns[startNodeId][endNodeId];
myStack.push(midNode);
while(midNode!=startNodeId)
{
midNode=wAns[startNodeId][midNode];
myStack.push(midNode);
}
printf("\n");
while(!myStack.isEmpty())
printf("%d ",myStack.pop());
/*Trace out all the path*/
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
startNodeId=i;
endNodeId=j;
myStack.push(endNodeId);
midNode=wAns[startNodeId][endNodeId];
myStack.push(midNode);
while(midNode!=startNodeId)
{
midNode=wAns[startNodeId][midNode];
myStack.push(midNode);
}
while(!myStack.isEmpty())
fprintf(outputFile,"%d,",myStack.pop());
fprintf(outputFile,"*");
}
fprintf(outputFile,"\r\n");
}
/******************End of Core program**********/
endTime=(double)clock()/(double)CLOCKS_PER_SEC;
tweenTime=endTime-startTime;/*Get the time collapsed*/
/*Time collapsed output*/
printf("the collapsed time in this algorithm implement is:%f\n",tweenTime);
fprintf(outputFile,"the collapsed time in this algorithm implement is:%f\r\n",tweenTime);
printf("\n*******end of test program******\n");
#endif
for(i=0;i<row;i++)
free(wArr[i]);
free(wArr);
printf("program end successfully,\n you have to preess any key to clean the buffer area to output,otherwise,you wiil not get the total answer.\n");
getchar();/*Screen Delay Control*/
return;
}
