知道CSDN上的牛人比较多。所以发这儿来了,万能的CSDN请帮帮我吧。
Your task is to implement Dijkstra's algorithm for a graph structure. The idea is that you create a graph from an input file (as you did/will do for your homework in Week 11) and then find the length of the shortest paths from a given vertex to all the other vertices. Your program should then print out the path lengths. Here, the vertices will be integers (int), for simplicity's sake. You don't need to use a Node or Vertex class (these are just names for the same thing, remember).
1. Dijkstra(G, source)
2. for each v in V(G)
3. set dist[v] to ∞ (infinity)
4. set previous[v] to undefined
5. dist[source] ← 0
6. let Q ← V(G)
7. while Q is not empty
8. u ← vertex v in Q with smallest dist[] value
9. if dist[u] = ∞
10. break
11. remove u from Q
12. for each neighbour v of u
13. let alt ← dist[u] + edge length(u,v)
14. if alt < dist[v]
15. dist[v] ← alt
16. previous[v] = u
17. return dist[]
For the input graph attached in the file "weightedgraph.png", which could be expressed by the adjacency matrix (assuming 0 means " no edge")
a b c d e f g h
a 0 2 1 3 5 7 0 0
b 2 0 3 0 0 0 0 0
c 1 3 0 0 0 0 0 0
d 3 0 0 0 0 0 9 0
e 5 0 0 0 0 1 4 0
f 7 0 0 0 1 0 0 3
g 0 0 0 9 4 0 0 0
h 0 0 0 0 0 3 0 0
The output should be
dist[] = [ 0 2 1 3 5 6 9 9 ]
Your task is to implement Dijkstra's algorithm for a graph structure. The idea is that you create a graph from an input file (as you did/will do for your homework in Week 11) and then find the length of the shortest paths from a given vertex to all the other vertices. Your program should then print out the path lengths. Here, the vertices will be integers (int), for simplicity's sake. You don't need to use a Node or Vertex class (these are just names for the same thing, remember).
1. Dijkstra(G, source)
2. for each v in V(G)
3. set dist[v] to ∞ (infinity)
4. set previous[v] to undefined
5. dist[source] ← 0
6. let Q ← V(G)
7. while Q is not empty
8. u ← vertex v in Q with smallest dist[] value
9. if dist[u] = ∞
10. break
11. remove u from Q
12. for each neighbour v of u
13. let alt ← dist[u] + edge length(u,v)
14. if alt < dist[v]
15. dist[v] ← alt
16. previous[v] = u
17. return dist[]
For the input graph attached in the file "weightedgraph.png", which could be expressed by the adjacency matrix (assuming 0 means " no edge")
a b c d e f g h
a 0 2 1 3 5 7 0 0
b 2 0 3 0 0 0 0 0
c 1 3 0 0 0 0 0 0
d 3 0 0 0 0 0 9 0
e 5 0 0 0 0 1 4 0
f 7 0 0 0 1 0 0 3
g 0 0 0 9 4 0 0 0
h 0 0 0 0 0 3 0 0
The output should be
dist[] = [ 0 2 1 3 5 6 9 9 ]
#include <stdio.h> #define INFINITY 10000
#define TRUE 1
#define FALSE 0
#define VERTEX_NUM 6
typedef struct Graph
{
char vexs[VERTEX_NUM]; /*顶点*/
int arcs[VERTEX_NUM][VERTEX_NUM]; /*邻接矩阵*/
int vexnum; /*顶点数*/
int arcnum; /*弧数*/
}Graph;
void ShortestPath(Graph g,int v0,int p[][VERTEX_NUM],int d[])
{
/*迪杰斯特拉算法求最短路径,g为图的邻接矩阵,v0为起始顶点,
p[v][w]储存v0到v路径上w的后继顶点(无后继置-1),d[v]为路径v0到v的带权长度*/
int v;
int w;
int min;
int i,j;
int final[VERTEX_NUM]; /*final[v]=TRUE当且仅当v属于S*/
/*初始化数组*/
for (v = 0; v < g.vexnum; v++)
{
final[v] = FALSE;
d[v] = g.arcs[v0][v];
for (w = 0; w < g.vexnum; w++)
{
p[v][w] = -1;
}
if (d[v] < INFINITY)
{
p[v][0] = v0;
p[v][1] = v;
}
}
/*初始化,顶点v0属于S集合*/
d[v0] = 0;
final[v0] = TRUE;
/*循环n-1次求最短路径*/
for (i = 1; i < g.vexnum; i++)
{
min=INFINITY;
for (w = 0; w<g.vexnum; w++)
{
if (!final[w]) /* w属于V-S */
{
if (d[w] < min)
{
/* w顶点离v0更近 */
v=w;
min=d[w];
}
}
}
final[v] = TRUE; /*离v0顶点最近的v加入S集*/
for (w = 0; w<g.vexnum; w++) /*更新当前最短路径及距离*/
{
if (!final[w] && (min+g.arcs[v][w] < d[w]) )
{
/*修改d[w]和p[w] (w属于V-S) */
d[w] = min + g.arcs[v][w];
for (j = 0; p[v][j]> -1 && j < VERTEX_NUM; j++)
{
p[w][j] = p[v][j]; /* p[w]=p[v] */
}
p[w][j] = w; /* p[w]=p[v]+w */
}
}
}
}
void main()
{
int i,
j;
Graph g;
int p[VERTEX_NUM][VERTEX_NUM];
int d[VERTEX_NUM];
int v0; /*初始化图g*/
g.vexs[0]='A',g.vexs[1]='B',g.vexs[2]='C',g.vexs[3]='D',g.vexs[4]='E',g.vexs[5]='F';
for(i=0;i<VERTEX_NUM;i++)
for(j=0;j<VERTEX_NUM;j++)
g.arcs[i][j]=INFINITY;
g.arcs[0][2]=10,g.arcs[0][4]=30,g.arcs[0][5]=100,g.arcs[1][2]=5,
g.arcs[2][3]=50,g.arcs[3][5]=10,g.arcs[4][3]=20,g.arcs[4][5]=60;
g.vexnum=g.arcnum=VERTEX_NUM; /*输出图的有关信息*/
for(i=0;i<VERTEX_NUM;i++)
{
printf("%c\t",g.vexs[i]);
for(j=0;j<VERTEX_NUM;j++)
{
printf("%5d ",g.arcs[i][j]);
}
printf("\n");
}
printf("\n"); /*求最短路径*/
v0 = 0;
ShortestPath(g,v0,p,d); /*输出最短路径*/
for (i = 0; i < g.vexnum; i++)
{
printf("Path %c to %c:\n",g.vexs[v0],g.vexs[i]);
if ( p[i][v0] != -1 ) /*存在路径则输出*/
{
for (j = 0; p[i][j]!=-1; j++)
{
if (j != 0)
printf("→");
printf(" %c",g.vexs[p[i][j]]);
}
printf("\n");
}
printf("Length:%d\n",d[i]);
printf("\n");
}
}
/**********************迪杰斯特拉算法*********************************************/
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/unix_net/archive/2009/05/06/4155975.aspx
你搜索这个了吗,不符合你的要求吗?
package graph;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* 定义简单图,为最短路径算法准备
* @author root
*
*/
public class SimplGraph {
/**
* 节点值
*/
public int key;
/**
* 相邻节点集合
*/
public List<Integer> nearNode;
/**
* 两节点之间的权重(距离)
*/
public Map<String,Integer> weight;
/**
* 初始化参数
* @param key
*/
public SimplGraph(int key){
this.key = key;
nearNode = new ArrayList<Integer>();
weight = new HashMap<String,Integer>();
}
/**
* 添加邻节点
* 张磊
*2007-6-23
*@param node
*@param lengh
*/
public void addNode(int node,int lengh){
//加入邻节点中
nearNode.add(node);
//记录类节点和node 节点的权重
weight.put(Integer.toString(node), lengh);
}
}
接下来是最短路径基本算法的实现类
package graph;
import java.util.Iterator;
/**
* 最短路径算法
* @author root
*
*/
public class Dijkstra {
SimplGraph[] total;
/**
* 初始化数据
*
*/
public Dijkstra(){
total = new SimplGraph[6];
//设置一个图
int a = 0,b = 1,c = 2,d = 3,e = 4,f = 5 ;
SimplGraph Sa = new SimplGraph(0);
SimplGraph Sb = new SimplGraph(9999);
SimplGraph Sc = new SimplGraph(9999);
SimplGraph Sd = new SimplGraph(9999);
SimplGraph Se = new SimplGraph(9999);
SimplGraph Sf = new SimplGraph(9999);
//设置每个节点的邻节点及权值
Sa.addNode(b,1);
Sa.addNode(c,4);
Sa.addNode(d,7);
Sb.addNode(a,1);
Sb.addNode(c,1);
Sb.addNode(e,3);
Sc.addNode(a,4);
Sc.addNode(b,1);
Sc.addNode(d,3);
Sc.addNode(f,6);
Sd.addNode(a,7);
Sd.addNode(c,3);
Sd.addNode(f,9);
Se.addNode(b,3);
Se.addNode(f,5);
Sf.addNode(c,6);
Sf.addNode(d,9);
Sf.addNode(e,5);
//设置每个节点的索引
total[a] = Sa;
total[b] = Sb;
total[c] = Sc;
total[d] = Sd;
total[e] = Se;
total[f] = Sf;
}
/**
* 最短路径计算(基本算法)
* 张磊
*2007-6-22
*/
public void minPath(){
for (int i = 0; i < total.length; i++) {
Iterator it = total[i].nearNode.iterator();
while(it.hasNext()){
//得到节点的数字索引
int node = (Integer)it.next();
//通过索引得到节点的类
SimplGraph sg = total[node];
//对此节点进行最短路径计算
if(sg.key>total[i].key+total[i].weight.get(Integer.toString(node)))
sg.key = total[i].key+total[i].weight.get(Integer.toString(node));
}
}
}
public static void main(String[] args){
Dijkstra d = new Dijkstra();
d.minPath();
SimplGraph[] s = d.total;
for (int i = 0; i < s.length; i++) {
System.out.println("节点 "+i);
System.out.println("最短路径为 "+s[i].key);
}
}
}
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/mohamode/archive/2007/07/26/1709895.aspx
23楼那个已经算可以了,只是没有按照我给的Graph来,把那个设置改成我的就行了。
哪位帮我做做吧,一百分归你了。
其他有帮助的我另外给分
Sc.addNode(f,6);
a b c d e f g h
a 0 2 1 3 5 7 0 0
b 2 0 3 0 0 0 0 0
c 1 3 0 0 0 0 0 0
d 3 0 0 0 0 0 9 0
e 5 0 0 0 0 1 4 0
f 7 0 0 0 1 0 0 3
g 0 0 0 9 4 0 0 0
h 0 0 0 0 0 3 0 0
这个队列中的结点间的长度不就完了,如a->a=0,a->b=2,a->c=1........如果结点间的长度等于0说明2个节点不相邻,就不用设Sa.addNode(和a相邻的节点,a到这个节点的长度);
再详细的我实在是没什么说了,如果你连这个都不会那么我建议你去看看书吧,给你个函数你都不会带值,哪不是不会的问题是学习态度的问题,
-------------业精于勤,荒于嬉,毁于惰。忘君珍重之!!!!!