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

news/2024/7/15 17:30:16 标签: c语言, 图论, c++

在这里插入图片描述

在这里插入图片描述

时间复杂度为 O(n^2)

#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);
}