shortestroad.txt

来自「这是大学中计算机专业学生的作业」· 文本 代码 · 共 103 行

#include<iostream>
using namespace std;

void Dijkstra(int sum , int DotFormer,int Distance[],int DotCurrently[],int **Line)
{
    int MaxDistance= 65535;//如果这条路径不存在就设它的权重是65535
    bool *s = new bool[sum];
    for (int i = 1; i <= sum; i++)
    {
        Distance[i] = Line[DotFormer][i];
        s[i] = false;
        if (Distance[i] == MaxDistance)
        {
            DotCurrently[i] = 0;
        }
        else
        {
            DotCurrently[i] = DotFormer;
        }
    }//S表示所有点的集合
    Distance[DotFormer] = 0;
    s[DotFormer] = true;
    for (int k = 1; k < sum; k++)
    {
        int temp = MaxDistance;
        int DotAfter = DotFormer;
        for (int l = 1; l <= sum; l++)
        {
            if ((!s[l]) && (Distance[l] < temp))
            {
                DotAfter = l;
                temp = Distance[l];
            }
        }
        s[DotAfter] = true;
        for (int j = 1; j <= sum; j++)
        {
            if ((!s[j]) && (Line[DotAfter][j] < MaxDistance))
            {
                int NewDistance = Distance[DotAfter] + Line[DotAfter][j];
                if (NewDistance < Distance[j])
                {
                    Distance[j] = NewDistance;
                    DotCurrently[j] = DotAfter;
                }
            }
        }
    }
}

void main()
{
    int sum,DotFormer,DotAim;
    int DotPassSum = 0;
	cout<<"please enter the number ot the dots:";
    cin>>sum;

    int *way = new int[sum + 1];
    int **Line = new int *[sum + 1];
    for (int i = 1; i <= sum; i++)
    {
        Line[i] = new int[sum + 1];
    }
    for (int j = 1; j <= sum; j++)
    {
        for (int t = j+1; t <= sum; t++)
        {
			cout<<"please enter the distance of the "<<j<<"th dot to the "<<t<<"th dot：";
            cin>>Line[j][t];
			Line[t][j]=Line[j][t];
        }
    }
    int *Distance = new int [sum];
    int *DotCurrently= new int [sum];
	
lp: cin>>DotFormer>>DotAim;
	if(DotFormer>sum||DotAim>sum)
	{
		cout<<"ERROR , please enter again."<<endl;
		goto lp;
		
	}


    Dijkstra(sum, DotFormer, Distance, DotCurrently, Line);
    cout<<"the distance the  shortcut  from the "<<DotFormer<<"th dot to the "<<DotAim<<"th dot:"<<Distance[DotAim]<<endl;
    int DotNonce = DotAim;
    while (DotNonce != DotFormer)
    {
        DotPassSum++;
        way[DotPassSum] = DotCurrently[DotNonce];
        DotNonce = DotCurrently[DotNonce];
    }

    cout<<"the shortcut:";
    for (int to = DotPassSum; to >= 1; to--)
    {
        cout<<way[to]<<" ->";
    }
    cout<<DotAim<<endl;

}