一个不知道怎么改的错误~~

时间：2021-09-29 09:26:47
这是最短路径的迪杰斯特拉算法的实现，在*处有个错误，应该怎么改呢？ 

//graph.h
#include<iostream>
using namespace std;
#define MAX 20
#define INF 32767
typedef struct{                                
	int arcs[MAX][MAX];                           //邻接矩阵
}Mgraph;

//main.cpp
#include<iostream>
#include "graph.h"
using namespace std;
void dijkstra(Mgraph gn,int vtxnum,int v0,int path[],int dist[]){
	int i;
	int s[MAX];                              //s用以标记那些已经找到最短路径的顶点，数组的初态只包括顶点v0，即s[0]=1
	dist[i] = gn.arcs[0][i];            //数组dist记录源点到其他各顶点当前的最短距离
	//初始化s,dist,path
	for(int v=0;v<vtxnum;v++){
		s[v] = 0;
		dist[v] = gn.arcs[v0][v];
		if(dist[v]<INF){
			path[v] = v0;
		}
		else{
			path[v] = -1;
		}
		dist[v0] = 0;
		s[v0] = 1;                              //初始时源点v0∈s
		for(int i=1;i<vtxnum-1;i++){
			int min = INF;
			v = -1;
			//找出最小的dist[w]
			for(int w=0;w<vtxnum;w++)
				if(!s[w]&&dist[w]<min){
					v = w;
					min = dist[w];
				}
				if(v==-1)  break;                        //已无顶点可加入，退出
				s[v] = 1;                                      //顶点v并入s
				//调整集合（V-S）中的各个顶点的距离值
				for(int j=0;j<vtxnum;j++){
					if(!s[j]&&(min+gn.arcs[v][j]<dist[j])){
						dist[j] = min+gn.arcs[v][j];
						path[j] = v;
					}
				}
		}
	}
}

int main(){
	int path[MAX];
	int dist[MAX];
	int vtxnum;
	int v0,n;
	Mgraph gn;
	cout<<"请输入图的顶点个数："<<"\n";
	cin>>vtxnum;
	gn.arcs[12][12] = {{0,15,4,7,INF,INF,INF,INF,INF,INF,INF,INF},  -----------------*
	{15,0,7,INF,15,12,INF,INF,INF,INF,INF,INF},
	{4,7,0,INF,16,INF,INF,INF,INF,INF,INF,INF},
	{7,INF,INF,0,8,INF,INF,INF,26,INF,INF,INF},
	{INF,15,16,8,0,20,18,INF,30,INF,INF,INF},
	{INF,12,INF,INF,20,0,INF,INF,INF,30,INF,INF,INF},
	{INF,INF,INF,18,INF,0,3,INF,16,INF,INF,INF},
	{INF,INF,INF,INF,INF,INF,3,0,7,INF,INF,INF},
	{INF,INF,INF,26,30,INF,INF,7,0,5,15,INF,INF},
	{INF,INF,INF,INF,INF,30,19,INF,5,0,INF,20},
	{INF,INF,INF,INF,INF,INF,INF,INF,15,INF,0,9},
	{INF,INF,INF,INF,INF,INF,INF,INF,INF,20,9,0}};
	cout<<"请输入所要求最短路径的顶点："<<"\n";
	cin>>v0;
	dijkstra(gn,vtxnum,v0,path,dist);
	cout<<"请输入"<<v0<<"要到的点："<<"\n";
	cin>>n;
	for(int i=0;i<=n;i++){
		cout<<"从"<<v0<<"到"<<n<<"的最短路径是："<<"\n";
		cout<<path[i]<<"------->"<<"\n";
	}
	system("pause");
	return 0;
}

在*处有个错误
IntelliSense: 应输入表达式 d:\visual studio 2010\program\dijkstra\dijkstra\main.cpp   dijkstra

11 个解决方案

#1

你那种只有在申明的时候才可以那样初始化，后面的初始化必须一个一个初始化

#2

定义了一个20×20的，赋值却变成12×12.。

#3

引用 1 楼 wh_liu 的回复:
你那种只有在申明的时候才可以那样初始化，后面的初始化必须一个一个初始化

正解。。

只有初始化时才能那么用。之后赋值不能那么写。

#4

这种初始化方式，不能 用在这里，应该是变量刚刚声明时用，比如 int i[10] = {0},你现在只能通过new，malloc来分配，然后逐个元素赋值

#5

你那种赋值只能在声明的时候用
你需要gn.arc[0][0] gn.arc[0][1]这样一个一个赋值

另外如果你不是为了日后扩展Mgraph结构体的话那么没有比较将一个二维数组放进一个专门的结构体中

#6

引用 5 楼 q191201771 的回复:
你那种赋值只能在声明的时候用
你需要gn.arc[0][0] gn.arc[0][1]这样一个一个赋值

另外如果你不是为了日后扩展Mgraph结构体的话那么没有比较将一个二维数组放进一个专门的结构体中

那这样就要赋值144次.....有没有别的方法呢？

#7

引用 6 楼 wjqwei 的回复:
引用 5 楼 q191201771 的回复:
你那种赋值只能在声明的时候用
你需要gn.arc[0][0] gn.arc[0][1]这样一个一个赋值

另外如果你不是为了日后扩展Mgraph结构体的话那么没有比较将一个二维数组放进一个专门的结构体中

那这样就要赋值144次.....有没有别的方法呢？

通过数组，循环赋值、

#8

问题已解决，谢谢大家~~

#9

引用 8 楼 wjqwei 的回复:
问题已解决，谢谢大家~~


/*以下仅供参考
Mgraph 是没有必要的，如果用它，可在程序中输入，很麻烦。
程序中的矩阵数据是以0开始的，最短路径的顶点应该为0。
如果换别的顶点，矩阵应该有改变，或能动态输入
形成矩阵。
顶点个数应该是12，小于它，有些顶点会有问题。
输出是逆向的。*/
#include<iostream>
using namespace std;
#define MAX 20
#define INF 32767
//typedef struct{                                
    //int arcs[MAX][MAX];                           //邻接矩阵
//}Mgraph;

void dijkstra(int gn[][12],int vtxnum,int v0,int path[],int dist[]){
    int i;
    int s[MAX];                              //s用以标记那些已经找到最短路径的顶点，数组的初态只包括顶点v0，即s[0]=1
    //dist[i] = gn[0][i];            //数组dist记录源点到其他各顶点当前的最短距离
    //初始化s,dist,path
    for(int v=0;v<vtxnum;v++){
        s[v] = 0;
        dist[v] = gn[v0][v];
        if(dist[v]<INF){
            path[v] = v0;
        }
        else{
            path[v] = -1;
        }
}//<------------------------here
        dist[v0] = 0;
        s[v0] = 1; 
//初始时源点v0∈s
        for( i=1;i<vtxnum;i++){
            int min = INF;
            v = -1;
            //找出最小的dist[w]
            for(int w=0;w<vtxnum;w++)
                if(!s[w]&&dist[w]<min){
                    v = w;
                    min = dist[w];
                }
                if(v==-1)  break;                        //已无顶点可加入，退出
                s[v] = 1;                                      //顶点v并入s
                //调整集合（V-S）中的各个顶点的距离值
                for(int j=0;j<vtxnum;j++){
                    if(!s[j]&&(min+gn[v][j]<dist[j])){
                        dist[j] = min+gn[v][j];
                        path[j] = v;
                    }
                }
        }
}

int main(){
    int path[MAX];
    int dist[MAX];
    int vtxnum;
    int v0,n;
    //Mgraph gn;
    //cout<<"请输入图的顶点个数："<<"\n";
    //cin>>vtxnum;
    int gn[12][12] = {{0,15,4,7,INF,INF,INF,INF,INF,INF,INF,INF}, 
    {15,0,7,INF,15,12,INF,INF,INF,INF,INF,INF},
    {4,7,0,INF,16,INF,INF,INF,INF,INF,INF,INF},
    {7,INF,INF,0,8,INF,INF,INF,26,INF,INF,INF},
    {INF,15,16,8,0,20,18,INF,30,INF,INF,INF},
    {INF,12,INF,INF,20,0,INF,INF,INF,30,INF,INF,},
    {INF,INF,INF,18,INF,0,3,INF,16,INF,INF,INF},
    {INF,INF,INF,INF,INF,INF,3,0,7,INF,INF,INF},
    {INF,INF,INF,26,30,INF,INF,7,0,5,15,INF},
    {INF,INF,INF,INF,INF,30,19,INF,5,0,INF,20},
    {INF,INF,INF,INF,INF,INF,INF,INF,15,INF,0,9},
    {INF,INF,INF,INF,INF,INF,INF,INF,INF,20,9,0}};

    cout<<"请输入图的顶点个数："<<"\n";
    cin>>vtxnum;

    cout<<"请输入所要求最短路径的顶点："<<"\n";
    cin>>v0;
    dijkstra(gn,vtxnum,v0,path,dist);
    cout<<"请输入"<<v0<<"要到的点："<<"\n";
    cin>>n;
    cout<<"从"<<v0<<"到"<<n<<"的最短路径是："<<"\n";
    //for(int i=0;i<12;i++){
        //cout<<"从"<<v0<<"到"<<n<<"的最短路径是："<<"\n";
        //cout<<path[i]<<"------->"<<"\n";
    // }

if (path[n])
{
do
{
cout<<path[n]<<"------>"<<n<<endl;
int temp =path[n];
n=temp;
}while(path[n]);
}
cout<<path[n]<<"------->"<<n<<endl;
    system("pause");
    return 0;
}

#10

上面说的
/*程序中的矩阵数据是以0开始的，最短路径的顶点应该为0。
如果换别的顶点，矩阵应该有改变，或能动态输入
形成矩阵。*/
有问题，可以是0以外的其他顶点。
当顶点是大于0时
这条语句为path[v] = 0;
或者直接为path[v] = 0;

#11

引用 10 楼 newfarmerchi 的回复:
上面说的
/*程序中的矩阵数据是以0开始的，最短路径的顶点应该为0。
如果换别的顶点，矩阵应该有改变，或能动态输入
形成矩阵。*/
有问题，可以是0以外的其他顶点。
当顶点是大于0时
这条语句为path[v] = 0;
或者直接为path[v] = 0;

^_^

#1

你那种只有在申明的时候才可以那样初始化，后面的初始化必须一个一个初始化

#2

定义了一个20×20的，赋值却变成12×12.。

#3

引用 1 楼 wh_liu 的回复:
你那种只有在申明的时候才可以那样初始化，后面的初始化必须一个一个初始化

正解。。

只有初始化时才能那么用。之后赋值不能那么写。

#4

这种初始化方式，不能 用在这里，应该是变量刚刚声明时用，比如 int i[10] = {0},你现在只能通过new，malloc来分配，然后逐个元素赋值

#5

你那种赋值只能在声明的时候用
你需要gn.arc[0][0] gn.arc[0][1]这样一个一个赋值

另外如果你不是为了日后扩展Mgraph结构体的话那么没有比较将一个二维数组放进一个专门的结构体中

#6

引用 5 楼 q191201771 的回复:
你那种赋值只能在声明的时候用
你需要gn.arc[0][0] gn.arc[0][1]这样一个一个赋值

另外如果你不是为了日后扩展Mgraph结构体的话那么没有比较将一个二维数组放进一个专门的结构体中

那这样就要赋值144次.....有没有别的方法呢？

#7

引用 6 楼 wjqwei 的回复:
引用 5 楼 q191201771 的回复:
你那种赋值只能在声明的时候用
你需要gn.arc[0][0] gn.arc[0][1]这样一个一个赋值

另外如果你不是为了日后扩展Mgraph结构体的话那么没有比较将一个二维数组放进一个专门的结构体中

那这样就要赋值144次.....有没有别的方法呢？

通过数组，循环赋值、

#8

问题已解决，谢谢大家~~

#9

引用 8 楼 wjqwei 的回复:
问题已解决，谢谢大家~~


/*以下仅供参考
Mgraph 是没有必要的，如果用它，可在程序中输入，很麻烦。
程序中的矩阵数据是以0开始的，最短路径的顶点应该为0。
如果换别的顶点，矩阵应该有改变，或能动态输入
形成矩阵。
顶点个数应该是12，小于它，有些顶点会有问题。
输出是逆向的。*/
#include<iostream>
using namespace std;
#define MAX 20
#define INF 32767
//typedef struct{                                
    //int arcs[MAX][MAX];                           //邻接矩阵
//}Mgraph;

void dijkstra(int gn[][12],int vtxnum,int v0,int path[],int dist[]){
    int i;
    int s[MAX];                              //s用以标记那些已经找到最短路径的顶点，数组的初态只包括顶点v0，即s[0]=1
    //dist[i] = gn[0][i];            //数组dist记录源点到其他各顶点当前的最短距离
    //初始化s,dist,path
    for(int v=0;v<vtxnum;v++){
        s[v] = 0;
        dist[v] = gn[v0][v];
        if(dist[v]<INF){
            path[v] = v0;
        }
        else{
            path[v] = -1;
        }
}//<------------------------here
        dist[v0] = 0;
        s[v0] = 1; 
//初始时源点v0∈s
        for( i=1;i<vtxnum;i++){
            int min = INF;
            v = -1;
            //找出最小的dist[w]
            for(int w=0;w<vtxnum;w++)
                if(!s[w]&&dist[w]<min){
                    v = w;
                    min = dist[w];
                }
                if(v==-1)  break;                        //已无顶点可加入，退出
                s[v] = 1;                                      //顶点v并入s
                //调整集合（V-S）中的各个顶点的距离值
                for(int j=0;j<vtxnum;j++){
                    if(!s[j]&&(min+gn[v][j]<dist[j])){
                        dist[j] = min+gn[v][j];
                        path[j] = v;
                    }
                }
        }
}

int main(){
    int path[MAX];
    int dist[MAX];
    int vtxnum;
    int v0,n;
    //Mgraph gn;
    //cout<<"请输入图的顶点个数："<<"\n";
    //cin>>vtxnum;
    int gn[12][12] = {{0,15,4,7,INF,INF,INF,INF,INF,INF,INF,INF}, 
    {15,0,7,INF,15,12,INF,INF,INF,INF,INF,INF},
    {4,7,0,INF,16,INF,INF,INF,INF,INF,INF,INF},
    {7,INF,INF,0,8,INF,INF,INF,26,INF,INF,INF},
    {INF,15,16,8,0,20,18,INF,30,INF,INF,INF},
    {INF,12,INF,INF,20,0,INF,INF,INF,30,INF,INF,},
    {INF,INF,INF,18,INF,0,3,INF,16,INF,INF,INF},
    {INF,INF,INF,INF,INF,INF,3,0,7,INF,INF,INF},
    {INF,INF,INF,26,30,INF,INF,7,0,5,15,INF},
    {INF,INF,INF,INF,INF,30,19,INF,5,0,INF,20},
    {INF,INF,INF,INF,INF,INF,INF,INF,15,INF,0,9},
    {INF,INF,INF,INF,INF,INF,INF,INF,INF,20,9,0}};

    cout<<"请输入图的顶点个数："<<"\n";
    cin>>vtxnum;

    cout<<"请输入所要求最短路径的顶点："<<"\n";
    cin>>v0;
    dijkstra(gn,vtxnum,v0,path,dist);
    cout<<"请输入"<<v0<<"要到的点："<<"\n";
    cin>>n;
    cout<<"从"<<v0<<"到"<<n<<"的最短路径是："<<"\n";
    //for(int i=0;i<12;i++){
        //cout<<"从"<<v0<<"到"<<n<<"的最短路径是："<<"\n";
        //cout<<path[i]<<"------->"<<"\n";
    // }

if (path[n])
{
do
{
cout<<path[n]<<"------>"<<n<<endl;
int temp =path[n];
n=temp;
}while(path[n]);
}
cout<<path[n]<<"------->"<<n<<endl;
    system("pause");
    return 0;
}

#10

上面说的
/*程序中的矩阵数据是以0开始的，最短路径的顶点应该为0。
如果换别的顶点，矩阵应该有改变，或能动态输入
形成矩阵。*/
有问题，可以是0以外的其他顶点。
当顶点是大于0时
这条语句为path[v] = 0;
或者直接为path[v] = 0;

#11

引用 10 楼 newfarmerchi 的回复:
上面说的
/*程序中的矩阵数据是以0开始的，最短路径的顶点应该为0。
如果换别的顶点，矩阵应该有改变，或能动态输入
形成矩阵。*/
有问题，可以是0以外的其他顶点。
当顶点是大于0时
这条语句为path[v] = 0;
或者直接为path[v] = 0;

^_^
标签：

相关文章