读书人
栏目▼

迪杰斯特拉算法真心不知道错在哪儿

发布时间： 2013-01-28 11:49:56 作者： rapoo

迪杰斯特拉算法，真心不知道错在哪里
近来课程设计老师让写一个最短路径，程序如下
#include<iostream>
#include<string.h>
using namespace std;
#define N 100
int i,j,temp[4];
//unsigned long distance[4][4];
unsigned long min;
char letter[N][N]={"行政楼","食堂","澡堂","实验室"};

//数据处理函数
void Min(int &ii,int &jj,int tem[],unsigned long &minn,unsigned long distances[4][4])
{
int h,m=0;
int k=0;
if(ii==1)//判断是不是第一次进入循环
{
minn=distances[tem[ii-1]][1];
}
else//取第一个非0的值为初始最小值
{
for(h=0;h<4;h++)
{
if((distances[tem[ii-1]][h]!=0)&&(distances[tem[ii-1]][h]!=-1))//第二次进入函数的时候因ii值已经增加，所以父节点在temp[ii-1]的地方
{
minn=distances[tem[ii-1]][h];
break;
}
}
}
for(jj=1;jj<4;jj++)//找到行的最小值
{
if(distances[tem[ii-1]][jj]!=0)
{
if(minn>distances[tem[ii-1]][jj])
{
minn=distances[tem[ii-1]][jj];
k=jj;
}
}
}
for(h=0;h<4;h++)
{
distances[h][k]=0;//因不可能构成回路，所以将最小值所在的列化为0
}

if(ii==1)
{
tem[ii]=k;//if i is the first value
//对节点进行标记
}
else
{
ii++;
tem[ii]=k;
}
for(h=1;h<4;h++)
{
if(distances[k][h]!=0)//分析在不等于0的情况下取值为无穷大和其他值
{
if(distances[k][h]!=-1)//取值不是无穷大
{
if(distances[k][h]+minn<distances[tem[ii-1]][h])
{
distances[k][h]=minn+distances[k][h];//若从最短路径加上值小于父节点的值则修改值
}
else
{
distances[tem[ii]][h]=distances[tem[ii-1]][h];
}
}
else//取值是无穷大时的比较
{
if(distances[tem[ii-1]][h]==-1);//判断需要比较的点是无穷大时不需要管他
else
distances[tem[ii]][h]=distances[tem[ii-1]][h];//判断需要比较的点不是无穷大时则将父节点的值给它
}
}
}
if(ii==1) ++ii;//当且仅当第一次时加一
}
int main()
{
unsigned long distance[4][4];//无穷大用-1表示故声明数组元素类型为无符号整形
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
distance[i][j]=0;//对成员进行初始化避免在引用时出错
}
}
for(i=0;i<3;i++)
{
for(j=i+1;j<4;j++)
{
cout<<"请输入"<<letter[i]<<"到"<<letter[j]<<"的距离(不能到达则用-1表示):"<<endl;;//输入数据时只需要输入一半的值
cin>>distance[i][j];
distance[j][i]=distance[i][j];
}
}
for(i=0;i<4;i++) distance[i][i]=0;//将矩阵的对角线初始化为0
for(i=0;i<4;i++) distance[i][0]=0;
for(i=0;i<4;i++)
{
temp[i]=0;
}

//以下是数据的处理过程
i=1;
j=1;
while(temp[3]==0)
{
Min(i,j,temp,min,distance);
//Min(i,j,temp,min,distance);
//Min(i,j,temp,min,distance);
}




//cout<<m[0]<<m[1]<<m[2]<<m[3]<<endl;;
cout<<"您输入的数据如下所示:"<<endl;//显示输入的数据
/*for(i=0;i<4;i++)
{
cout<<letter[i]<<" ";
}
cout<<endl;*/
for( i=0;i<4;i++)
{
for(int k=0;k<4;k++)
{

cout<<distance[i][k]<<" ";
}
cout<<endl;
}
for(i=0;i<4;i++) cout<<temp[i]<<" ";

return 0;
}
我发现第二次进入函数的时候k的值竟然是0，还有我知道这里我的终止条件有问题但不知怎么改，求助！！！！！！！！


[解决办法]
先把算法思想弄清楚了再写代码 出错的时候才能够找得出来
[解决办法]

/***************************************
 * About:    有向图的Dijkstra算法实现
 * Author:   Tanky Woo
 * Blog:     www.WuTianQi.com
 ***************************************/
  
 #include <iostream>
 using namespace std;
  
 const int maxnum = 100;
 const int maxint = 999999;
  
  
 void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
 {
     bool s[maxnum];    // 判断是否已存入该点到S集合中
     for(int i=1; i<=n; ++i)
     {
         dist[i] = c[v][i];
         s[i] = 0;     // 初始都未用过该点
         if(dist[i] == maxint)
             prev[i] = 0;
         else
             prev[i] = v;
     }
     dist[v] = 0;
     s[v] = 1;
  
     // 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
     // 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度
     for(int i=2; i<=n; ++i)
     {
         int tmp = maxint;
         int u = v;
         // 找出当前未使用的点j的dist[j]最小值
         for(int j=1; j<=n; ++j)
             if((!s[j]) && dist[j]<tmp)
             {
                 u = j;              // u保存当前邻接点中距离最小的点的号码
                 tmp = dist[j];
             }
         s[u] = 1;    // 表示u点已存入S集合中
  
         // 更新dist
         for(int j=1; j<=n; ++j)
             if((!s[j]) && c[u][j]<maxint)
             {
                 int newdist = dist[u] + c[u][j];
                 if(newdist < dist[j]) 
 
                 {
                     dist[j] = newdist;
                     prev[j] = u;
                 }
             }
     }
 }
  
 void searchPath(int *prev,int v, int u)
 {
     int que[maxnum];
     int tot = 1;
     que[tot] = u;
     tot++;
     int tmp = prev[u];
     while(tmp != v)
     {
         que[tot] = tmp;
         tot++;
         tmp = prev[tmp];
     }
     que[tot] = v;
     for(int i=tot; i>=1; --i)
         if(i != 1)
             cout << que[i] << " -> ";
         else
             cout << que[i] << endl;
 }
  
 int main()
 {
     freopen("input.txt", "r", stdin);
     // 各数组都从下标1开始
     int dist[maxnum];     // 表示当前点到源点的最短路径长度
     int prev[maxnum];     // 记录当前点的前一个结点
     int c[maxnum][maxnum];   // 记录图的两点间路径长度
     int n, line;             // 图的结点数和路径数
  
     // 输入结点数
     cin >> n;
     // 输入路径数
     cin >> line;
     int p, q, len;          // 输入p, q两点及其路径长度
  
     // 初始化c[][]为maxint
     for(int i=1; i<=n; ++i)
         for(int j=1; j<=n; ++j)
             c[i][j] = maxint;
  
     for(int i=1; i<=line; ++i)  
     {
         cin >> p >> q >> len;
         if(len < c[p][q])       // 有重边
         {
             c[p][q] = len;      // p指向q 
 
             c[q][p] = len;      // q指向p，这样表示无向图
         }
     }
  
     for(int i=1; i<=n; ++i)
         dist[i] = maxint;
     for(int i=1; i<=n; ++i)
     {
         for(int j=1; j<=n; ++j)
             printf("%8d", c[i][j]);
         printf("\n");
     }
  
     Dijkstra(n, 1, dist, prev, c);
  
     // 最短路径长度
     cout << "源点到最后一个顶点的最短路径长度: " << dist[n] << endl;
  
     // 路径
     cout << "源点到最后一个顶点的路径为: ";
     searchPath(prev, 1, n);
 }

输出数据:
999999 10 999999 30 100
10 999999 50 999999 999999
999999 50 999999 20 10
30 999999 20 999999 60
100 999999 10 60 999999
源点到最后一个顶点的最短路径长度: 60
源点到最后一个顶点的路径为: 1 -> 4 -> 3 -> 5
[解决办法]

#pragma once
#include<iostream>
#include<fstream>
#include"F:\QQPCmgr\documents\visual studio 2010\Projects\Graph\Graph_matrix\GraphAdjMatrix.h"
using namespace std;

template<class T, class E>
void DijkstraAlgorithm(GraphAdjMatrix<T,E> &targetG, const T &beginVertex, E dist[], int path[])
{
int verticesNum = targetG.GetVerticesNum(); //获取图顶点数目
int beginIdx = targetG.GetVerticesPos(beginVertex); //获取源顶点索引值(在这里都是用顶点索引值代表顶点的)
bool *state = new bool[verticesNum]; //一个状态值数组，用来表示已求得的最短路径顶点集
E weigth_temp, minWeight; //辅助求最短路径变量
E maxWeightFlag = targetG.GetMaxWeight(); //获取图中约定好的代表顶点之间不可达的权值标示

for(int i = 0; i < verticesNum; i++) //循环用来做初始化信息
{
dist[i] = targetG.GetWeight(beginIdx, i); //dist[]数组中最初存放源点能直接到达的点的边权值(这个以后会根据算法的进行慢慢更新的)
state[i] = false; //把所有的状态值都置为false 表示都没有求出最短路径
if((i != beginIdx) && (dist[i] != maxWeightFlag)) //不等于源点并且源点与顶点i之间有边
{
path[i] = beginIdx; //pre = path[i]表示：能最近到达i顶点的上一步是pre(算法只着眼于能到达本顶点路径长度最短的上一个顶点，通过回溯可以一步一步的回溯到源点)
}
else
{
path[i] = -1; //表示:到达顶点i路径长度最短的上一个顶点不存在,意味着不存在源点到达顶点i最短路径
}
}

state[beginIdx] = true; //算法起始：将源点放入已求得最短路径顶点集合中
dist[beginIdx] = 0; //从源点到达源点的边权值为0

for(int count = 0; count < verticesNum-1; count++) //总共循环图定点数目-1次
{
minWeight = maxWeightFlag;
int nextIdx; //此索引记录：当前dist[]中值最小的那一个(通过循环实现)
for(int i = 0; i < verticesNum; i++)
{
if((state[i] == false) && (dist[i] < minWeight)) 
 
{
minWeight = dist[i];
nextIdx = i;
}
}

state[nextIdx] = true; //可以认为：就目前来看源点到达nextIdx的路径是最短的,将其放入状态数组中
//站在nextIdx顶点的角度来看，是否能借助于我，使得源点到达其他顶点的路径会更短呢？下面是搜索与判断，更新
for(int k = 0; k < verticesNum; k++)
{
weigth_temp = targetG.GetWeight(nextIdx, k);
//如果确实通过nextIdx顶点使得源点到达顶点k的路径更小了，执行下面if语句
if((state[k] == false)&&(weigth_temp != maxWeightFlag)&&(dist[nextIdx] + weigth_temp < dist[k]))
{
dist[k] = dist[nextIdx] + weigth_temp;
path[k] = nextIdx; //这时要修改能够最短到达顶点k的上一个顶点
}
}

}//外层大循环

}

template<class T, class E>
void PrintShortestPath(GraphAdjMatrix<T,E> &targetG, const T &beginVertex, E dist[], int path[])
{
int begVtxNum = targetG.GetVerticesPos(beginVertex); //获取源点索引
int verticesNum = targetG.GetVerticesNum();
int temp, count;
int *tempDist = new int[verticesNum]; //用来存储源点到达其他的任意一个顶点的路径信息(存储的仍然是顶点索引)

for(int vtxnum = 0; vtxnum < verticesNum; vtxnum++) //搜索所有的顶点
{
if(vtxnum != begVtxNum) //不能对源点输出最短路径
{
temp = vtxnum;
count = 0;

while(temp != begVtxNum)
{
tempDist[count++] = temp; //先把目的顶点vtxnum的索引放入辅助数组tempDist[]中
temp = path[temp]; //回溯找到源点
}
cout<<"顶点:<"<<targetG.GetVertex(vtxnum)<<">的最短路径:"<<beginVertex<<" ";
while(count > 0)
{
cout<<targetG.GetVertex(tempDist[--count])<<" "; //对辅助数组进行逆向输出
}
cout<<"最短路径长度为:"<<dist[vtxnum]<<endl;
}
}

delete []tempDist;
}


[解决办法]
#include<iostream>
#include<string.h>
using namespace std;
#define N 100

//数据处理函数
void Min(int &ii,int &jj,int tem[],unsigned long &minn,unsigned long distances[4][4])
{
int h,m=0;
int k=0;
if(ii==1) //判断是不是第一次进入循环
{ 
minn=distances[tem[ii-1]][1];
}
else //取第一个非0的值为初始最小值
{
for(h=0;h<4;h++)
{
if((distances[tem[ii-1]][h]!=0)&&(distances[tem[ii-1]][h]!=-1)) //第二次进入函数的时候因ii值已经增加，所以父节点在temp[ii-1]的地方
{
minn=distances[tem[ii-1]][h];
break;
}
} 
}
for(jj=1;jj<4;jj++) //找到行的最小值 
{ 
if(distances[tem[ii-1]][jj]!=0)
{
if(minn>distances[tem[ii-1]][jj])
{
minn=distances[tem[ii-1]][jj];
k=jj;
}
} 
}
for(h=0;h<4;h++) 
{
distances[h][k]=0; //因不可能构成回路，所以将最小值所在的列化为0
}

if(ii==1)  
{
tem[ii]=k; //if i is the first value 
//对节点进行标记
}
else 
{
ii++;
tem[ii]=k;
}
for(h=1;h<4;h++)
{
if(distances[k][h]!=0) //分析在不等于0的情况下取值为无穷大和其他值 
{ 
if(distances[k][h]!=-1) //取值不是无穷大
{
if(distances[k][h]+minn<distances[tem[ii-1]][h])
{
distances[k][h]=minn+distances[k][h]; //若从最短路径加上值小于父节点的值则修改值 
} 
 
else
{
distances[tem[ii]][h]=distances[tem[ii-1]][h]; 
}
}
else //取值是无穷大时的比较
{
if(distances[tem[ii-1]][h]==-1) ; //判断需要比较的点是无穷大时不需要管他
else
distances[tem[ii]][h]=distances[tem[ii-1]][h]; //判断需要比较的点不是无穷大时则将父节点的值给它
}
}
}
if(ii==1) ++ii; //当且仅当第一次时加一
}
int  main()
{
int i,j,temp[4];
//unsigned long distance[4][4];
unsigned long min;
char letter[N][N]={"行政楼","食堂","澡堂","实验室"};


unsigned long distance[4][4]; //无穷大用-1表示故声明数组元素类型为无符号整形
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
distance[i][j]=0; //对成员进行初始化避免在引用时出错
}
}
for(i=0;i<3;i++)
{
for(j=i+1;j<4;j++)
{
cout<<"请输入"<<letter[i]<<"到"<<letter[j]<<"的距离(不能到达则用-1表示):"<<endl;; //输入数据时只需要输入一半的值
cin>>distance[i][j];
distance[j][i]=distance[i][j];
} 
}
for(i=0;i<4;i++)  distance[i][i]=0; //将矩阵的对角线初始化为0
for(i=0;i<4;i++)  distance[i][0]=0;
for(i=0;i<4;i++)
{
temp[i]=0;
}

//以下是数据的处理过程
i=1;
j=1;
while(temp[3]==0)
{
Min(i,j,temp,min,distance);
//Min(i,j,temp,min,distance);
//Min(i,j,temp,min,distance);
}


//cout<<m[0]<<m[1]<<m[2]<<m[3]<<endl;;
cout<<"您输入的数据如下所示:"<<endl; // 显示输入的数据
/*for(i=0;i<4;i++)
{
cout<<letter[i]<<" ";
}
cout<<endl;*/
for( i=0;i<4;i++)
{
for(int k=0;k<4;k++)
{

cout<<distance[i][k]<<"    "; 
} 
cout<<endl;
}
for(i=0;i<4;i++) cout<<temp[i]<<" ";

return 0;
}

读书人网 >C++

热点推荐

触屏版 | 电脑版

读书人网 m.reader8.net