2627: 贪心算法-单源最短路径

#include<stdio.h>
#define MAXVEX 100 // 最大顶点数由用户定义
#define INFINITY  65535

typedef char VertexType; // 顶点类型应由用户定义
typedef int EdgeType; // 边上的权值类型应由用户定义

typedef struct {
	VertexType vexs[MAXVEX];
	EdgeType arc[MAXVEX][MAXVEX];
	int numNodes;
	int numEdges;
} MGraph;

int label[MAXVEX]; // 存储从源点出发到其余各个顶点的最短路径上的最后一个顶点编号
int distance[MAXVEX]; // 存储从源点出发到其余各个顶点的最短距离

void CreateGraph(MGraph &G) {
	int i,j,u,v,w;
	for(i=0; i<G.numNodes; i++) // 初始化邻接矩阵
		for(j=0; j<G.numNodes; j++) G.arc[i][j] = INFINITY;
	for(i=0; i<G.numEdges; i++) { // 输入边信息填写有向图的邻接矩阵
		scanf("%d %d %d",&u,&v,&w);  // 边的信息包括顶点1，顶点2以及它们之间的距离
		G.arc[u][v]=w;
	}
}

void Dijkstra(MGraph G, int v) { //求从顶点v出发到其它各顶点的最短距离

	int i,j,found[MAXVEX]= {0}; // found[i]表示编号为i的顶点是否已经找到最短路径，1表示找到，0表示没有找到    
    found[v]=1;
	for(j=0; j<G.numNodes; j++) {// 建立初始待定路径表，设置父顶点的编号
		distance[j]=G.arc[v][j];
		label[j]=v;
	}
	for(i=1; i<G.numNodes; i++) {
		int min = INFINITY; // 查找从顶点v出发到“剩余”顶点的最短距离
		int index;
		for(j=0; j<G.numNodes; j++){
				
				
		}
		found[index]=1; // 设置编号为index的顶点已经找到最短路径
		for(j=0; j<G.numNodes; j++){ //更新待定路径表以及父顶点的编号 ) 
				
		}
	}
}

void Output(MGraph G, int v) {
	int n=G.numNodes;
	for(int i=0; i<n; i++) { //按照指定格式输出从源点v到其余各点的最短距离及其路径
		if(i!=v) {
			printf("v%d-v%d:%d[v%d",v,i,distance[i],i);
			for(int u=i; u!=v; u=label[u]) printf("<-v%d",label[u]);
			printf("]\n");
		}
	}
}

int main(void) {
	MGraph graph;
	scanf("%d %d",&graph.numNodes,&graph.numEdges);
	CreateGraph(graph); //存储结构是邻接矩阵
	Dijkstra(graph, 0); //求从顶点0出发到其余各个顶点的最短距离及其路径
	Output(graph, 0); //打印从顶点0出发到其余各个顶点的最短距离及其路径
	return 0;
}

4 4
0 1 10
0 2 30
1 3 20
2 3 40

v0-v1:10[v1<-v0]
v0-v2:30[v2<-v0]
v0-v3:30[v3<-v1<-v0]