基于Dijkstra算法的最短路径问题求解

Question

进行类的设计与实现，解决最短路径问题。具体要求如下：
（1） 采用图的邻接矩阵或邻接表实现最短路径问题中图的存储；
（2） 采用Dijkstra算法求从某个源点到其余各顶点的最短路径；
（3） 将上述功能作为类的成员函数实现，编写主函数测试上述功能。
(4) 用C++编写
现在分就这么多了，如果能帮上忙，以后有分肯定补上，现在只有这些了，有分肯定补上，多多的补，保证，一定，帮帮忙吧，着急啊。能运行的。

Answer 1

// 最短路.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<stdio.h>
const int MAX=1000;
const int INF=1000000000;
public class SPFA
{
public: int n;//表示图里面的点数

public: int path[MAX][MAX];//定义链接矩阵最多是1000个点

public: int dis[MAX];//定义源点到其他点的距离

public: int src;//定义源点

SPFA();
public:void Cal()
{
int i,j,k;
bool used[MAX]={false};//定义点是否访问过了,初始化为未访问
for(i=0;i<n;i++)//初始化一下到各个点的距离
{
dis[i]=path[src][i];
}
dis[src]=0;
int min_=INF;
for(i=0;i<n;i++)
{
k=-1;
min_=INF;
for(j=0;j<n;j++)
{
if(dis[j]<min_&&!used[j])
{
min_=dis[j];
k=j;
}
}
if(k==-1)//已经找不到有路可走的点
{
return;
}
for(j=0;j<n;j++)
{
if(!used[j]&&dis[j]>min_+path[k][j])//如果从k点走到j点的路很比原来的要短，那么更新
{
dis[j]=min_+path[k][j];
}
}
}
}
};

int _tmain(int argc, _TCHAR* argv[])
{
//按照下面的数据格式输入,-1表示没有路,自己到自己是0
/*
3
0 1 2
3 0 -1
3 4 0
*/

SPFA a=new SPFA();
printf("请输入点数");
scanf("%d", &a.n);
int i,j;
for(i=0;i<a.n;i++)
{
for(j=0;j<a.n;j++)
{
scanf("%d",&a.path[i][j]);
if(a.path[i][j]==-1)
{
a.path[i][j]=INF;
}
}
}
a.src=0;//源点暂时定为0，你自己改吧
a.Cal();
for(i=0;i<a.n;i++)
{
printf("dis[%d]=%d\n",i,a.dis[i]);
}
return 0;
}

//你看一下吧，我这里定义了类运行不了，算法是对的。请给分

追问

谢谢谢谢，好人做到底，你能不能再改一下，把它整运行了啊，这题对于你来说也许很简单，也花费不了你多少时间，可我不会改啊，分肯定给你，而且多多的给你，如果你能帮忙整好了，以后一定赚更多得分给你，真的真的，再次感谢，希望尽快收到你的回复，帮个忙吧，马上就要交作业了，我的邮箱642205377@qq.com，谢谢谢谢。而且能不能用c++编写啊，在线等你的好消息，敬候佳音，真希望你能帮个忙，谢谢谢谢。

追答

好的，我是用C++编译器写的啊，用的是VS2008，可是运行不了，我看看是什么原因
// 最短路.cpp : 定义控制台应用程序的入口点。
//

//#include "stdafx.h"
#include
const int MAX=1000;
const int INF=1000000000;
class SPFA
{
public: int n;//表示图里面的点数

public: int path[MAX][MAX];//定义链接矩阵最多是1000个点

public: int dis[MAX];//定义源点到其他点的距离

public: int src;//定义源点

public:void Cal()
{
int i,j,k;
bool used[MAX]={false};//定义点是否访问过了,初始化为未访问
for(i=0;imin_+path[k][j])//如果从k点走到j点的路很比原来的要短，那么更新
{
dis[j]=min_+path[k][j];
}
}
}
}
};

//int _tmain(int argc, _TCHAR* argv[])
int main()
{
//按照下面的数据格式输入,-1表示没有路,自己到自己是0
/*
3
0 -1 -1
3 0 -1
3 4 0

3
0 100 1
3 0 -1
3 4 0

3
0 1 2
3 0 -1
3 4 0
*/

SPFA* a=new SPFA();
printf("请输入点数");
scanf("%d", &a->n);
int i,j;
for(i=0;in;i++)
{
for(j=0;jn;j++)
{
scanf("%d",&a->path[i][j]);
if(a->path[i][j]==-1)
{
a->path[i][j]=INF;
}
}
}
a->src=0;//源点暂时定为0，你自己改吧
a->Cal();
for(i=0;in;i++)
{
printf("dis[%d]=%d\n",i,a->dis[i]);
}
return 0;
}

好了，现在OK了，刚才算法里面有一个小BUG改正了

追问

不是，我说的是编译语言用c++，这个不是c么，我们是c++课设，真心的希望，麻烦您再帮我改一下吧，分已经给你了，好人做到底，希望你能帮一下忙，改完了，发我邮箱就可以了，希望你在帮一下下，我们马上就要交作业了，拜托，谢谢谢谢，谢谢谢谢。

Answer 2

#include<iostream>
using namespace std;
const int MAX=1000;
const int INF=10000;
class SPFA
{
public:
int n;//表示图里面的点数
int path[MAX][MAX];//定义链接矩阵最多是1000个点
int dis[MAX];//定义源点到其他点的距离
int src;//定义源点
void Cal()
{
int i,j,k;
bool used[MAX]={false};//定义点是否访问过了,初始化为未访问
for(i=0;i<n;i++)//初始化一下到各个点的距离
{
dis[i]=path[src][i];
}
dis[src]=0;
int min_=INF;
for(i=0;i<n;i++)
{
k=-1;
min_=INF;
for(j=0;j<n;j++)
{
if(dis[j]<min_&&!used[j])
{
min_=dis[j];
k=j;
}
}
if(k==-1)//已经找不到有路可走的点
{
return;
}
used[k]=true;
for(j=0;j<n;j++)
{
if(!used[j]&&dis[j]>min_+path[k][j])//如果从k点走到j点的路很比原来的要短，那么更新
{
dis[j]=min_+path[k][j];
}
}
}
}
};

int main()
{cout<<"当两个点是不可达点时则该值为10000:"<<endl;
freopen("in.txt","r",stdin);
SPFA* a=new SPFA();
cout<<"请输入点数:";
cin>>a->n;
cout<<a->n<<endl;
int i,j;
for(i=0;i<a->n;i++)
{
for(j=0;j<a->n;j++)
{
cin>>a->path[i][j];
if(a->path[i][j]==-1)
{
a->path[i][j]=INF;
}
}
}
cout<<"该图的加权矩阵为:"<<endl;
for(i=0;i<a->n;i++)
{ for(j=0;j<a->n;j++)
cout<<a->path[i][j]<<" ";
cout<<endl;
}
a->src=0;//源点暂时定为0，你自己改吧
a->Cal();
cout<<"当源点为"<<a->src<<"到各点的最短路径为:";
for(i=0;i<a->n;i++)
{
cout<<a->dis[i]<<" ";
}
cout<<endl;
return 0;
}