• 大小: 157KB
    文件类型: .zip
    金币: 1
    下载: 0 次
    发布日期: 2021-01-07
  • 语言: 其他
  • 标签: 最短距离  

资源简介

目前网络上电子地图的使用很普遍。利用电子地图可以很方便地确定从一个地点到另一个地点的路径。特别地,可确定在城市中的公交换乘路线。 电子地图可以看成是一个图,而公交线路图可看成是带权有向图G =(V,E),其中每条边的权是非负实数。 最短路径问题:计算从给定的起点s到另一个顶点t的最短路径的长度。 你的任务:对给定的一个(无向)图G,及G中的两点s、t,计算从起点s到顶点t的最短距离。

资源截图

代码片段和文件信息

/*#include  
#include  
using namespace std; 
void Dijkstra(int nint vint dist[]int prev[]int **c) 

int maxint = 65535; 
//int maxint = -1; 
bool *s = new bool[n]; 
for (int i = 1; i <= n; i++) 

dist[i] = c[v][i]; 
s[i] = false; 
if (dist[i] == maxint) 
prev[i] = 0; 
else 
prev[i] = v; 


dist[v] = 0; 
s[v] = true; 
for (int i = 1; i < n; i++) 

int temp = maxint; 
int u = v; 
for (int j = 1; j <= n; j++) 

if ((!s[j]) && (dist[j] < temp)) 
//if ((!s[j]) && (dist[j] >= temp)) 
{   
u = j; 
temp = dist[j]; 
}  


s[u] = true; 

for (int j = 1; j <= n; j++) 
{   

if ((!s[j]) && (c[u][j] < maxint)) 
//if ((!s[j]) && (c[u][j] >= maxint)) 
{   

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        3654  2015-07-03 18:09  4-c\4-c.cpp
     文件        1433  2015-07-03 18:09  4-c\4-c.msp
     目录           0  2015-07-04 14:11  4-c\Debug\
     文件      547378  2015-07-03 18:09  4-c\Debug\4-c.exe
     文件      126698  2015-07-03 18:09  4-c\Debug\4-c.o
     目录           0  2015-07-04 14:11  4-c\

评论

共有 条评论