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

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

#include "stdafx.h"
#include
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 {
dis[i]=path[src][i];
}
dis[src]=0;
int min_=INF;
for(i=0;i {
k=-1;
min_=INF;
for(j=0;j {
if(dis[j] {
min_=dis[j];
k=j;
}
}
if(k==-1)//已经找不到有路可走的点
{
return;
}
for(j=0;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 {
for(j=0;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 {
printf("dis[%d]=%d\n",i,a.dis[i]);
}
return 0;
}

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

#include
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 {
dis[i]=path[src][i];
}
dis[src]=0;
int min_=INF;
for(i=0;i {
k=-1;
min_=INF;
for(j=0;j {
if(dis[j] {
min_=dis[j];
k=j;
}
}
if(k==-1)//已经找不到有路可走的点
{
return;
}
used[k]=true;
for(j=0;j {
if(!used[j]&&dis[j]>min_+path[k][j])//如果从k点走到j点的路很比原来的要短，那么更新
{
dis[j]=min_+path[k][j];
}
}
}
}
};

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