最短路径-迪杰斯特拉算法-单源最短路径

本文主要是介绍最短路径-迪杰斯特拉算法-单源最短路径，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<stdio.h>
#include<stdlib.h>
#define BOOL int
#define TRUE 1
#define FALSE 0
#define T int
#define SIZE 6
#define MAXNUMBER 99
typedef struct graph {
	int NoEdge;
	int Vertices;
	int** A;
}Graph;
void CreateGraph(Graph* g, int n, int noedge) {
	int i, j;
	g->NoEdge = noedge;
	g->Vertices = n;
	g->A = (int**)malloc(n * sizeof(int*));
	for (i = 0; i < n; i++) {
		g->A[i] = (int*)malloc(n * sizeof(int));
		for (j = 0; j < n; j++) {
			g->A[i][j] = noedge;
		}
		g->A[i][i] = 0;
	}
}
void Add(Graph* g, int u, int v, int w) {
	if (u < 0 || v < 0 || u > g->Vertices - 1 || v>g->Vertices - 1 || u == v || g->A[u][v] != g->NoEdge) {
		printf("BadInput\n");
	}
	else {
		g->A[u][v] = w;
	}
}
int ChooseMin(T d[], int n, BOOL s[], T MaxNumber) {
	int i, minpos ;
	T min=MaxNumber;
	for ( i = 0; i < n; i++)
	{
		if (d[i]<=min&& !s[i])
		{
			min = d[i];
			minpos = i;
		}
	}
	return minpos;
}
void Dijkstra(Graph *g, int v ) {
	int i, u, w, n = g->Vertices;
	T d[SIZE] = { 0 };
	T path[SIZE] = { 0 };
	BOOL s[SIZE] = {FALSE};
	if (v<0|| v> n-1)
	{
		printf("输错了\n");
		return;
	}
	for ( i = 0; i < n; i++)
	{
		s[i] = FALSE;
		d[i] = g->A[v][i];
		if (i!=v && d[i]<g->NoEdge)
		{
			path[i] = v;
		}
		else {
			path[i] = -1;
		}
	}
	s[v] = TRUE; d[v] = 0;
	for ( i = 1; i <= n-1; i++)
	{
		u = ChooseMin(d, n, s, g->NoEdge);
		s[u] = TRUE;
		for (w = 0; w < n; w++)
		{
			if (!s[w] && d[u]+g->A[u][w]<d[w])
			{
				d[w] = d[u] + g->A[u][w];
				path[w] = u;
			}
		}
	}
	for ( i = 0; i < n; i++)
	{
		printf("%d ", s[i]);
	}
	printf("\n");
	for (i = 0; i < n; i++)
	{
		printf("%d ", d[i]);
	}
	printf("\n");
	for (i = 0; i < n; i++)
	{
		printf("%d ", path[i]);
	}
	printf("\n");
}
void Delete(Graph* g, int u, int v) {
	if (u < 0 || v < 0 || u > g->Vertices - 1 || v>g->Vertices - 1 || u == v || g->A[u][v] == g->NoEdge) {
		printf("BadInput\n");
	}
	else {
		g->A[u][v] = g->NoEdge;
		printf("Delete Successfully\n");
	}
}
void Exist(Graph* g, int u, int v) {
	if (u < 0 || v < 0 || u > g->Vertices - 1 || v>g->Vertices - 1 || u == v || g->A[u][v] == g->NoEdge) {
		printf("No Existance\n");
	}
	else {
		printf("Element Exists!\n");
	}
}
void PrintMatrix(Graph* g) {
	int i, j;
	for (i = 0; i < g->Vertices; i++) {
		for (j = 0; j < g->Vertices; j++) {
			printf("%-4d", g->A[i][j]);
		}
		printf("\n");
	}
	printf("***************\n");
}
void main() {
	Graph* g;
	g = (Graph*)malloc(sizeof(Graph));
	CreateGraph(g, SIZE, MAXNUMBER); //在这里网的noedge统一为99，可以看出这是创建了一个网
	PrintMatrix(g);
	Add(g, 0, 1, 50);
	Add(g, 0, 2, 10);
	Add(g, 0, 4, 70);
	Add(g, 1, 2, 15);
	Add(g, 1, 4, 10);
	Add(g, 2, 0, 20);
	Add(g, 2, 3, 15);
	Add(g, 3, 1, 20);
	Add(g, 3, 4, 35);
	Add(g, 4, 3, 30);
	Add(g, 5, 3, 3);
	PrintMatrix(g);
	Dijkstra(g, 0);
}

0 99 99 99 99 99
99 0 99 99 99 99
99 99 0 99 99 99
99 99 99 0 99 99
99 99 99 99 0 99
99 99 99 99 99 0

0 50 10 99 70 99
99 0 15 99 10 99
20 99 0 15 99 99
99 20 99 0 35 99
99 99 99 30 0 99
99 99 99 3 99 0

1 1 1 1 1 1
0 45 10 25 55 99
-1 3 0 2 1 -1

这篇关于最短路径-迪杰斯特拉算法-单源最短路径的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！