6-17 Shortest Path [2](25 分)
2024-08-26 01:21:26
Write a program to find the weighted shortest distances from any vertex to a given source vertex in a digraph. It is guaranteed that all the weights are positive.
Format of functions:
void ShortestDist( MGraph Graph, int dist[], Vertex S );
where MGraph
is defined as the following:
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;
The shortest distance from V to the source S is supposed to be stored in dist[V]. If V cannot be reached from S, store -1 instead.
Sample program of judge:
#include <stdio.h>
#include <stdlib.h>
typedef enum {false, true} bool;
#define INFINITY 1000000
#define MaxVertexNum 10 /* maximum number of vertices */
typedef int Vertex; /* vertices are numbered from 0 to MaxVertexNum-1 */
typedef int WeightType;
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;
MGraph ReadG(); /* details omitted */
void ShortestDist( MGraph Graph, int dist[], Vertex S );
int main()
{
int dist[MaxVertexNum];
Vertex S, V;
MGraph G = ReadG();
scanf("%d", &S);
ShortestDist( G, dist, S );
for ( V=0; V<G->Nv; V++ )
printf("%d ", dist[V]);
return 0;
}
/* Your function will be put here */
Sample Input (for the graph shown in the figure):
7 9
0 1 1
0 5 1
0 6 1
5 3 1
2 1 2
2 6 3
6 4 4
4 5 5
6 5 12
2
Sample Output:
-1 2 0 13 7 12 3
不能抵达的为INFINITY,用过dijkstra算法,最后记得把INFINITY变成-1,dist[S]变成0
代码:
void ShortestDist( MGraph Graph, int dist[], Vertex S )
{
for(int i = ;i < Graph -> Nv;i ++)
dist[i] = Graph -> G[S][i];
int vis[MaxVertexNum] = {};
vis[S] = ;
for(int i = ;i < Graph -> Nv;i ++)
{
int min = INFINITY;
int t = INFINITY;
for(int j = ;j < Graph -> Nv;j ++)
if(!vis[j]&&dist[j] < min)min = dist[j],t = j;
if(min == INFINITY)continue;
vis[t] = ;
for(int j = ;j < Graph -> Nv;j ++)
{
if(!vis[j])
{
if(dist[j] > Graph -> G[t][j] + min)dist[j] = Graph -> G[t][j] + min;
}
}
}
for(int i = ;i < Graph -> Nv;i ++)
if(i == S)dist[i] = ;
else if(dist[i] == INFINITY)dist [i] = -;
}
最新文章
- Js(DOM) 和Jq 对象的相互转换
- mysql分页查询详解
- php对csv文件的读取,写入,输出下载操作
- 如何修改 EM12c 中 SYSMAN 用户的密码?
- 【英语】Bingo口语笔记(39) - Get系列
- vi 命令 使用方法
- Projected Coordinate Systems
- Oracle--常见Exception
- sql的临时表使用小结
- 【转】 iOS开发UI篇—UIScrollView控件实现图片轮播
- EffectiveC#5--始终提供ToString()
- HNCU1324:算法2-2:有序线性表的有序合并(线性表)
- Redis Cluster部署、管理和测试
- HighCharts之2D含有负值的面积图
- Oracle 如何对中文字段进行排序
- SQL SERVER 一个SQL语句的执行顺序
- [转]StarWind模拟iSCSI设备
- [Jmeter]Xpath获取元素某个属性的值,以及获取最后一个元素某个属性的值
- equals方法变量和常量位置区别
- HAProxy负载均衡原理及企业级实例部署haproxy集群
热门文章
- Spring—Ioc
- 2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) Solution
- 11月26号host
- Spring 整合Mybatis 出现了Cause: org.springframework.jdbc.CannotGetJdbcConnectionException: Could not get JDBC Connection; nested exception is org.apache.commons.dbcp.SQLNestedException: Cannot create Poola
- 2017-2018-2 20165207实验二《Java面向对象程序设计》实验报告
- TED #01#
- 微信小程序:全局配置app.json
- (转载)Ubuntu 16.04+1080Ti机器学习基本环境配置
- Same Tree,判断两个二叉树是不是相同的树,结构相同,每个节点的值相同
- R语言画图小结