迪杰斯特拉算法，真心不知道错在哪里
近来课程设计老师让写一个最短路径，程序如下
#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);
}
#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;
}
