Dijkstra--簡易版 （最短路徑）

Dijkstra算法思路：

G={V,E}

1. 初始時令 S={V0},T=V-S={其餘頂點}，T中頂點對應的距離值

若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值

若不存在<V0,Vi>，d(V0,Vi)為∞

2. 從T中選取一個與S中頂點有關聯邊且權值最小的頂點W，加入到S中

3. 對其餘T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值

重複上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

#include<stdio.h>
#include<memory.h>
#define MAX 1000000

int graph[100][100];   //存放鄰接矩陣   0表示兩點之間沒有邊 

int vertex[100];  //該點的最短路徑是否找到

int dis[100];    //存放begin點到i的最短距離

void Creat_G(int vertnum){
	memset(graph,0,sizeof(graph));
	
	printf("輸入圖的鄰接矩陣：\n");
	
	int i,j;
	for(i=1;i<=vertnum;i++){
		for(j=1;j<=vertnum;j++){
			scanf("%d",&graph[i][j]);
		}
	}
	
	printf("建立完成\n----------------------\n");
} 

void Dijkstra(int begin,int vertnum){
	
	memset(vertex,0,sizeof(vertex));
	vertex[begin]=1;	
	int i,j;
	for(i=1;i<=vertnum;i++){
		if(i==begin) dis[i]=0;
		else dis[i]= MAX;
	}
	for(j=1;j<=vertnum;j++){
		int min=MAX;	//用于記錄目前最小的那個點 
		int key=begin;
		for(i=1;i<=vertnum;i++){
			if(!vertex[i]){
				if(graph[begin][i] && graph[begin][i]+dis[begin]<dis[i]){
					dis[i] = graph[begin][i]+dis[begin];
				}
				if(dis[i]<min){
					min=dis[i];
					key=i;
				}	
			}
		}
		vertex[key]=1;    //将目前找到的那個最小值标記為已找到
		begin=key;        //更新begin的值
	}
}

int main(){
	int num;
	printf("輸入點的個數：\n");
	scanf("%d",&num);
	printf("-------------------------\n");
	Creat_G(num);
	int begin=3;
	for(begin=1;begin<=num;begin++){
		Dijkstra(begin,num);
		int i;
		for(i=1;i<=num;i++)
			printf("<%d,%d> = %d\t",begin,i,dis[i]);
			printf("\n");
	}
	return 0;
}