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

成都創(chuàng)新互聯(lián)堅信：善待客戶，將會成為終身客戶。我們能堅持多年，是因為我們一直可值得信賴。我們從不忽悠初訪客戶，我們用心做好本職工作，不忘初心，方得始終。10多年網(wǎng)站建設(shè)經(jīng)驗成都創(chuàng)新互聯(lián)是成都老牌網(wǎng)站營銷服務(wù)商,為您提供成都做網(wǎng)站、網(wǎng)站建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、網(wǎng)站設(shè)計、H5響應(yīng)式網(wǎng)站、網(wǎng)站制作、品牌網(wǎng)站設(shè)計、微信小程序定制開發(fā)服務(wù),給眾多知名企業(yè)提供過好品質(zhì)的建站服務(wù)。

算法基本思想和過程

     單源最短路徑問題，即在圖中求出給定頂點到其它任一頂點的最短路徑。在弄清楚如何求算單源最短路徑問題之前，必須弄清楚最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)。

一.最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)

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

假設(shè)P(i,j)={Vi....Vk..Vs...Vj}是從頂點i到j(luò)的最短路徑，則有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(luò)的最短路徑相矛盾。因此該性質(zhì)得證。

二.Dijkstra算法

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

    假設(shè)存在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;

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

//鄰接矩陣法圖的生成函數(shù)
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("請輸入相應(yīng)的的鄰接矩陣:\n");
	for( i=0; i<VertexNum; i++ )
		for( j=0; j<VertexNum; j++ )
			scanf("%d", &g->edg[i][j]);
}

//打印圖的結(jié)點標(biāo)識符和鄰接矩陣
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");
	}
}

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

//將不鄰接的頂點之間的權(quán)值設(shè)置為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求最短路徑函數(shù)
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 );					//設(shè)置權(quán)值

	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集合，對距離數(shù)組distance進行更新，比較原路徑長度與以新加入的頂點為中間點的路徑長度
				distance[k] = distance[j] + g.edg[j][k];
			}

		parent[index++] = j;
	}

	printf("%c到%c的最短路徑經(jīng)過頂點依次為:\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;
}

測試數(shù)據(jù)及結(jié)果

看完上述內(nèi)容，你們掌握Dijkstra算法求最短路徑問題完整C代碼怎么寫的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

文章標(biāo)題：Dijkstra算法求最短路徑問題完整C代碼怎么寫
標(biāo)題URL：http://jinyejixie.com/article42/gggiec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、標(biāo)簽優(yōu)化、品牌網(wǎng)站設(shè)計、網(wǎng)站收錄、網(wǎng)站排名、域名注冊

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)