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

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

算法基本思想和過程

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

一.最短路徑的最優(yōu)子結構性質

   該性質描述為：如果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代碼怎么寫的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業(yè)資訊頻道，感謝各位的閱讀！