亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

Dijkstra算法求最短路徑問題完整C代碼怎么寫

發布時間:2021-10-14 14:23:07 來源:億速云 閱讀:495 作者:柒染 欄目:編程語言

Dijkstra算法求最短路徑問題完整C代碼怎么寫,相信很多沒有經驗的人對此束手無策,為此本文總結了問題出現的原因和解決方法,通過這篇文章希望你能解決這個問題。

算法基本思想和過程

     單源最短路徑問題,即在圖中求出給定頂點到其它任一頂點的最短路徑。在弄清楚如何求算單源最短路徑問題之前,必須弄清楚最短路徑的最優子結構性質。

一.最短路徑的最優子結構性質

   該性質描述為:如果P(i,j)={Vi....Vk..Vs...Vj}是從頂點i到j的最短路徑,k和s是這條路徑上的一個中間頂點,那么P(k,s)必定是從k到s的最短路徑。下面證明該性質的正確性。

假設P(i,j)={Vi....Vk..Vs...Vj}是從頂點i到j的最短路徑,則有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是從k到s的最短距離,那么必定存在另一條從k到s的最短路徑P'(k,s),那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。則與P(i,j)是從i到j的最短路徑相矛盾。因此該性質得證。

二.Dijkstra算法

    由上述性質可知,如果存在一條從i到j的最短路徑(Vi.....Vk,Vj),Vk是Vj前面的一頂點。那么(Vi...Vk)也必定是從i到k的最短路徑。為了求出最短路徑,Dijkstra就提出了以最短路徑長度遞增,逐次生成最短路徑的算法。譬如對于源頂點V0,首先選擇其直接相鄰的頂點中長度最短的頂點Vi,那么當前已知可得從V0到達Vj頂點的最短距離dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根據這種思路,

    假設存在G=<V,E>,源頂點為V0,U={V0},dist[i]記錄V0到i的最短距離,path[i]記錄從V0到i路徑上的i前面的一個頂點。

1.從V-U中選擇使dist[i]值最小的頂點i,將i加入到U中;

2.更新與i直接相鄰頂點的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})

3.直到U=V,停止。

完整C代碼

<pre name="code" class="cpp">/* Dijkstra算法求圖的最短路徑問題C代碼 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MaxSize 20
#define INFINITY 65535

typedef char VertexType;

 //定義圖 的鄰接矩陣表示法結構
typedef struct Graph {
	VertexType ver[MaxSize+1];
	int edg[MaxSize][MaxSize];
}Graph;

//鄰接矩陣法圖的生成函數
void CreateGraph( Graph *g )
{
	int i = 0;
	int j = 0;
	int VertexNum;
	VertexType Ver;

	printf("請輸入圖的頂點:\n");
	while( '\n' != (Ver=getchar()) )
		g->ver[i++] = Ver;
	g->ver[i] = '\0';

	VertexNum = strlen(g->ver);
	printf("請輸入相應的的鄰接矩陣:\n");
	for( i=0; i<VertexNum; i++ )
		for( j=0; j<VertexNum; j++ )
			scanf("%d", &g->edg[i][j]);
}

//打印圖的結點標識符和鄰接矩陣
void PrintGraph( Graph g )
{
	int i, j;
	int VertexNum = strlen(g.ver);
	printf("圖的頂點為:\n");
	for( i=0; i<VertexNum; i++ )
		printf("%c ", g.ver[i]);
	printf("\n");

	printf("圖的鄰接矩陣為:\n");
	for( i=0; i<VertexNum; i++ ) {
		for( j=0; j<VertexNum; j++ )
			printf("%d ", g.edg[i][j]);
		printf("\n");
	}
}

//求圖的頂點數
int CalVerNum( Graph g )
{
	return strlen(g.ver);
}

//將不鄰接的頂點之間的權值設置為INFINITY
void SetWeight( Graph *g )
{
	for( int i=0; i<CalVerNum(*g); i++ )
		for( int j=0; j<CalVerNum(*g); j++ )
			if( 0 == g->edg[i][j] )
				g->edg[i][j] = INFINITY;
}

//Dijkstra求最短路徑函數
void Dijkstra( Graph g )
{
	int VertexNum = CalVerNum( g );
	int j;
	int mini;
	int index = 0;
	int *used = (int *)malloc(sizeof(int)*VertexNum);
	int *distance = (int *)malloc(sizeof(int)*VertexNum);
	int *parent = (int *)malloc(sizeof(int)*VertexNum);
	int *last = (int *)malloc(sizeof(int)*VertexNum);

	SetWeight( &g );					//設置權值

	for( int i=0; i<VertexNum; i++ ) {
		used[i] = 0;
		distance[i] = g.edg[0][i];   //初始化為與編號為0的頂點的距離
		last[i] = 0;
	}

	used[0] = 1;
	parent[index++] = 0;

	for( i=0; i<VertexNum-1; i++ ) {
		j = 0;
		mini = INFINITY;

		for( int k=0; k<VertexNum; k++ )
			if( (0 == used[k]) && (distance[k] < mini) ) {
				mini = distance[k];
				j = k;			//j為剛剛找到的V-U中到源點路徑最短的頂點
			}
		
		used[j] = 1;

		for( k=0; k<VertexNum; k++ ) 
			if( (0 == used[k]) && (distance[k] > distance[j] + g.edg[j][k]) ) {   //由于有頂點新加入U集合,對距離數組distance進行更新,比較原路徑長度與以新加入的頂點為中間點的路徑長度
				distance[k] = distance[j] + g.edg[j][k];
			}

		parent[index++] = j;
	}

	printf("%c到%c的最短路徑經過頂點依次為:\n", g.ver[0], g.ver[VertexNum-1]);
	for( i=0; i<index; i++ )
		printf("%c ", g.ver[parent[i]]);
	printf("\n");

	printf("最短路徑長度為: %d\n", mini);
	
}

int main()
{
	Graph g;
	CreateGraph( &g );
	PrintGraph( g );

	Dijkstra( g );
	return 0;
}

測試數據及結果
Dijkstra算法求最短路徑問題完整C代碼怎么寫

Dijkstra算法求最短路徑問題完整C代碼怎么寫

看完上述內容,你們掌握Dijkstra算法求最短路徑問題完整C代碼怎么寫的方法了嗎?如果還想學到更多技能或想了解更多相關內容,歡迎關注億速云行業資訊頻道,感謝各位的閱讀!

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

海晏县| 安宁市| 承德市| 综艺| 商洛市| 老河口市| 天台县| 大同县| 犍为县| 平和县| 共和县| 图们市| 昭平县| 轮台县| 安吉县| 恩平市| 当雄县| 肥乡县| 盐山县| 孟津县| 泰安市| 广州市| 南乐县| 德化县| 正镶白旗| 东丰县| 任丘市| 宁夏| 教育| 民乐县| 古蔺县| 淮南市| 安平县| 湟中县| 蒙阴县| 长武县| 高唐县| 咸阳市| 呼伦贝尔市| 大足县| 河北区|