一、最短總距離算法:

1.描述

我們先來分析一下這個問題。某個地區n個城市構成一個交通圖,我們可以使用圖結構來描述這個問題，其對應關系如下:

這樣，求解各個城市之間的最短總距離問題就歸結為該圖的最小生成樹問題。

2.最小生成樹

一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，並且有保持圖連通的最少的邊。如圖：

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPGgyPjMuu/mxvsu8z+s8L2gyPgo8cD48YnI+CjwvcD4KPHA+ICAgICAgICC82cnoR6O9KFajrEUpysfBrM2otcSjrFRFysdHyc/X7tChyfqzycr31tCx37XEvK+6z6Gjy+O3qLTTVaO9e3UwfaOodTChylajqaGiVEWjvXt9v6rKvKGj1ti4tNa00NDPwsHQstnX96O6PGJyPgogICAgICAgICAgINTay/nT0HWhylWjrHahylajrVW1xLHfKHWjrHYpocpF1tDV0tK7zPXIqCYjMjA1NDA71+7QobXEsd8odTAsdjApsqLI67yvus9URdbQo6zNrMqxdjCyosjrVaOs1rG1vVajvVXOqta5oaM8YnI+CiAgICAgICAgICAgtMvKsaOsVEXW0LHY09BuLTHM9bHfo6xUPShWo6xURSnOqke1xNfu0KHJ+rPJyvehozwvcD4KPHA+PGJyPgo8L3A+CjxoMj40Lsq1z9a0+sLrKNfutszX3L7gwOvL47eoKTwvaDI+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;">#include #include #include #define MaxNum 20 //圖的最大頂點數 #define MaxValue 65535 //最大值 #define USED 0; //已選用頂點 #define NoL -1 //非鄰接頂點 typedef struct { char Vertex[MaxNum]; //保存頂點信息(序號或字母) int GType; //圖的類型(0:無向圖,1) int VertexNum; //頂點的數量 int EdgeNum; //邊的數量 int EdgeWeight[MaxNum][MaxNum]; //保存邊的權 int isTrav[MaxNum]; //定義鄰接矩陣圖結構 }GraphMatrix; void CreateGraph(GraphMatrix *GM) { int i,j,k; int weight; char EstartV,EendV; std::cout<<"輸入圖中各頂點信息\n"; for (i = 0; iVertexNum; i++) { getchar(); printf("第%d個頂點:",i+1); scanf("%c",&(GM->Vertex[i])); } std::cout<<"輸入構成各邊的頂點及權值:\n"; for (k = 0; k EdgeNum; k++) { getchar(); printf("第%d條邊:",k+1); scanf("%c %c %d",&EstartV,&EendV,&weight); for ( i= 0; EstartV != GM->Vertex[i]; i++); for ( j= 0; EendV != GM->Vertex[j]; j++); GM->EdgeWeight[i][j] = weight; if (GM->GType == 0) //若是無向圖 { GM->EdgeWeight[j][i] = weight; } } } void ClearGraph(GraphMatrix *GM) { int i,j; for (i=0; iVertexNum; i++) { for (j=0; jVertexNum; j++) { GM->EdgeWeight[i][j] = MaxValue; } } } void OutGraph(GraphMatrix *GM) { int i,j; for (j=0; jVertexNum; j++) { printf("\t%c",GM->Vertex[j]); } std::cout<<"\n"; for (i=0; iVertexNum; i++) { printf("%c",GM->Vertex[i]); for (j=0; jVertexNum; j++) { if (GM->EdgeWeight[i][j] == MaxValue) { printf("\tZ"); //以Z表示無窮大 } else { printf("\t%d",GM->EdgeWeight[i][j]); //輸出邊的權值 } } std::cout<<"\n"; } } void PrimGraph(GraphMatrix GM) //最小生成樹算法 { int i,j,k,min,sum; int weight[MaxNum]; //權值 char vtempx[MaxNum]; //臨時頂點信息 sum = 0; for(i = 1; i0) //到具有更小權值的未使用邊 { min = weight[j]; //保存權植 k = j; //保存鄰接點序號 } } sum +=min; //權值累加 printf("(%c,%c),",vtempx[k],GM.Vertex[k]); //輸出生成樹一條邊 vtempx[k] = USED; weight[k] = MaxValue; for (j = 0; j
演示結果:

演示效果圖:

二、最短路徑

1.描述

求解城市之間的最短距離是一個非常實際的問題。其大意如下:

某個地區有n個城市,如何選擇路線使某個城市到某個指定城市的距離最短?

注：這裡需要求解的最短路徑指兩個城市之間的最短距離，面不是所有城市之間最短總距離。

2.基本思想

算法步驟如下：

1. 初始時令 S={V0},T={其余頂點}，T中頂點對應的距離值
若存在，d(V0,Vi)為弧上的權值
若不存在，d(V0,Vi)為∞
2. 從T中選取一個其距離值為最小的頂點W且不在S中，加入S
3. 對其余T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值
重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

3.實現代碼

#include 
#include 
#include 

#define MaxNum 20           //圖的最大頂點數
#define MaxValue 65535      //最大值
int  path[MaxNum];          //兩點經過的頂點集合的數組
int tmpvertex[MaxNum];      //最短路徑的起始點集合

#define USED 0;             //已選用頂點
#define NoL -1              //非鄰接頂點

typedef struct
{
	char Vertex[MaxNum];            //保存頂點信息(序號或字母)
	int GType;                      //圖的類型(0:無向圖,1)
	int VertexNum;                  //頂點的數量
	int EdgeNum;                    //邊的數量
	int EdgeWeight[MaxNum][MaxNum]; //保存邊的權
	int isTrav[MaxNum];             //定義鄰接矩陣圖結構
}GraphMatrix;

void CreateGraph(GraphMatrix *GM)
{
	int i,j,k;
	int weight;
	char EstartV,EendV;
    
	std::cout<<"輸入圖中各頂點信息\n";
	for (i = 0; iVertexNum; i++)
	{
		getchar();
		printf("第%d個頂點:",i+1);
		scanf("%c",&(GM->Vertex[i]));
	}
	std::cout<<"輸入構成各邊的頂點及權值:\n";
	for (k = 0; k EdgeNum; k++)
	{
		getchar();
		printf("第%d條邊:",k+1);
		scanf("%c %c %d",&EstartV,&EendV,&weight);
		for ( i= 0; EstartV != GM->Vertex[i]; i++);
		for ( j= 0; EendV != GM->Vertex[j]; j++);
		GM->EdgeWeight[i][j] = weight;
		if (GM->GType == 0) //若是無向圖
		{
			GM->EdgeWeight[j][i] = weight;
		}
	}
}

void ClearGraph(GraphMatrix *GM)
{
	int i,j;
	for (i=0; iVertexNum; i++)
	{
		for (j=0; jVertexNum; j++)
		{
			GM->EdgeWeight[i][j] = MaxValue;
		}
	}
}

void OutGraph(GraphMatrix *GM)
{
	int i,j;
	for (j=0; jVertexNum; j++)
	{
		printf("\t%c",GM->Vertex[j]);
	}
	std::cout<<"\n";
    
	for (i=0; iVertexNum; i++)
	{
		printf("%c",GM->Vertex[i]);
		for (j=0; jVertexNum; j++)
		{
			if (GM->EdgeWeight[i][j] == MaxValue)
			{
				printf("\tZ");  //以Z表示無窮大
			}
			else
			{
				printf("\t%d",GM->EdgeWeight[i][j]);  //輸出邊的權值
			}
		}
		std::cout<<"\n";
	}
}

void DisMin(GraphMatrix GM,int vend)    //最短路徑算法
{
    int weight[MaxNum];                 //某終止點到各頂點的最短路徑長度
    int i,j,k,min;
    vend--;
    
    for (i =0; i0)  //有效權值
        {
            path[i] = vend;                     //保存邊
        }
    }
    
    for (i=0; i演示結果:

                





演示效果圖:



                





參考書籍:《C/C++常用算法手冊》