无向图最短路径
题目描述
​	    求无向图中任意两个顶点之间的最短路径。
输入格式
​	    输入数据第一行是一个正整数，表示图中的顶点个数n（顶点将分别按0，1，…，n-1进行编号，n < 1000）。之后的n行每行都包含n个整数，第i行第j个数表示顶点i-1和顶点j-1之间的边长，用10000来表示两个顶点之间无边。后面每行2个数字，表示一对待求最短路径的顶点，用-1 -1表示输入结束，-1 -1不求解。
输出格式
​		每对待求最短路径的顶点输出两行数据：第一行输出两个顶点间的最短路径长度，第二行输出最短路径，要按顺序输出顶点编号序列，顶点间用空格隔开。当两个顶点间没有路径时，只在一行上输出字符串“NO”。
样例输入
7
0 12 10000 10000 10000 10000 10000
12 0 10000 10000 3 10000 10000
10000 10000 0 10000 10000 21 11
10000 10000 10000 0 10000 10000 10000
10000 3 10000 10000 0 10000 8
10000 10000 21 10000 10000 0 10000
10000 10000 11 10000 8 10000 0
0 2
0 3
5 0
2 1
1 5
-1 -1	

样例输入
34
0 1 4 6 2
NO
55
5 2 6 4 1 0
22
2 6 4 1
43
1 4 6 2 5

个人题解（不知道对不对）
​		思路跟着程序走一遍就了解了。
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#define MAX 10000
using namespace std;

int myGraph[1005][1005]; 					//存放邻接矩阵
int n;										//点数

struct {
	int result = MAX;						//res[i].result表示源点到i的最短路径
	int virgin = 1;							//res[i].virgin表示该点是否被访问过
	int last = -1;							//res[i].last记录该点的上一个节点
}res[1005];									//res[i]
//初始化res数组，每次求最短路之前需先进行初始化
void myInit() {
	for(int i = 0; i < n; ++i) {
		res[i].last = -1;
		res[i].result = MAX;
		res[i].virgin = 1;
	}
}
//通过广度优先搜索解决该问题
void myBPS(int start) {
	queue<int> myQueue;
	myQueue.push(start);
	res[start].virgin = 0;						//记得start已经不是virgin了
	res[start].result = 0;						//记得start到start路径长度为0
    //队列空则说明已经求得从start到图中每一个节点的最短路径
	while(!myQueue.empty()) {
		int pop = myQueue.front();
		myQueue.pop();
        //每个节点都走走看
		for(int i = 0; i < n; ++i) {
			if(myGraph[pop][i] != MAX && i != pop) {
                //更新res[i].result
				if(res[i].result > res[pop].result + myGraph[pop][i]) {
					res[i].result = res[pop].result + myGraph[pop][i];
					res[i].last = pop;
                    //res[i].result被更新也要把他后序节点随之更新，所以要加入队列再来一次
					myQueue.push(i);
				}
                //是virgin就加进队列
				if(res[i].virgin == 1) {
					myQueue.push(i);
					res[i].virgin = 0;
				}
			}
		}
	}
}
//主函数
int main() {
    cin >> n;
	//输入邻接矩阵
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            cin >> myGraph[i][j];
        }
    }

    while(1) {
        int start, end;
        cin >> start >> end;
        myInit();								//初始化res数组，(我才没有傻到把它放到myBPS后)
        myBPS(start);							//对该图进行BPS搜索

        if(start == -1) {						//判定程序结束条件
            break;
        } else if(res[end].result == MAX) {		//res[end].result == MAX说明无法到达该点
            cout << "NO" << endl;
        } else if(start == end) {				//源点即为终点
            cout << "0" << endl;
            cout << start << endl;
        } else {
            cout << res[end].result << endl;
            stack<int> myStack;					//从end到start将res[i].last存入栈中
            myStack.push(end);
            while(res[end].last != -1) {
                myStack.push(res[end].last);
                end = res[end].last;
            }
            while(!myStack.empty()){
                cout << myStack.top() << " ";	//输出栈中元素即为所求路径
                myStack.pop();
            }
            cout << endl;
        }		
    }
    return 0;

} 

一心想学习算法，很少去真正静下心来去研究，前几天趁着周末去了解了最短路径的资料，用python写了一个最短路径算法。算法是基于带权无向图去寻找两个点之间的最短路径，数据存储用邻接矩阵记录。首先画出一幅无向图如下，标出各个节点之间的权值。
其中对应索引：
A ——> 0
B ——> 1
C ——> 2
D ——>3
E ——> 4
F ——> 5
G ——> 6
邻接矩阵表示无向图：
算法思想是通过Dijkstra算法结合自身想法实现的。大致思路是：从起始点开始，搜索周围的路径，记录每个点到起始点的权值存到已标记权值节点字典A，将起始点存入已遍历列表B，然后再遍历已标记权值节点字典A，搜索节点周围的路径，如果周围节点存在于表B，比较累加权值，新权值小于已有权值则更新权值和来源节点，否则什么都不做；如果不存在与表B，则添加节点和权值和来源节点到表A，直到搜索到终点则结束。
这时最短路径存在于表A中，得到终点的权值和来源路径，向上递推到起始点，即可得到最短路径，下面是代码：
#-*-coding:utf-8 -*-
classDijkstraExtendPath():def __init__(self, node_map):
self.node_map=node_map
self.node_length=len(node_map)
self.used_node_list=[]
self.collected_node_dict={}def __call__(self, from_node, to_node):
self.from_node=from_node
self.to_node=to_node
self._init_dijkstra()returnself._format_path()def_init_dijkstra(self):
self.used_node_list.append(self.from_node)
self.collected_node_dict[self.from_node]= [0, -1]for index1, node1 inenumerate(self.node_map[self.from_node]):ifnode1:
self.collected_node_dict[index1]=[node1, self.from_node]
self._foreach_dijkstra()def_foreach_dijkstra(self):if len(self.used_node_list) == self.node_length - 1:return
for key, val in self.collected_node_dict.items():  #遍历已有权值节点
if key not in self.used_node_list and key !=to_node:
self.used_node_list.append(key)else:continue
for index1, node1 in enumerate(self.node_map[key]):  #对节点进行遍历
#如果节点在权值节点中并且权值大于新权值
if node1 and index1 in self.collected_node_dict and self.collected_node_dict[index1][0] > node1 +val[0]:
self.collected_node_dict[index1][0]= node1 + val[0] #更新权值
self.collected_node_dict[index1][1] =keyelif node1 and index1 not inself.collected_node_dict:
self.collected_node_dict[index1]= [node1 +val[0], key]
self._foreach_dijkstra()def_format_path(self):
node_list=[]
temp_node=self.to_node
node_list.append((temp_node, self.collected_node_dict[temp_node][0]))while self.collected_node_dict[temp_node][1] != -1:
temp_node= self.collected_node_dict[temp_node][1]
node_list.append((temp_node, self.collected_node_dict[temp_node][0]))
node_list.reverse()returnnode_listdefset_node_map(node_map, node, node_list):for x, y, val innode_list:
node_map[node.index(x)][node.index(y)]= node_map[node.index(y)][node.index(x)] =valif __name__ == "__main__":
node= [‘A‘, ‘B‘, ‘C‘, ‘D‘, ‘E‘, ‘F‘, ‘G‘]
node_list= [(‘A‘, ‘F‘, 9), (‘A‘, ‘B‘, 10), (‘A‘, ‘G‘, 15), (‘B‘, ‘F‘, 2),
(‘G‘, ‘F‘, 3), (‘G‘, ‘E‘, 12), (‘G‘, ‘C‘, 10), (‘C‘, ‘E‘, 1),
(‘E‘, ‘D‘, 7)]
node_map= [[0 for val in xrange(len(node))] for val inxrange(len(node))]
set_node_map(node_map, node, node_list)#A -->; D
from_node = node.index(‘A‘)
to_node= node.index(‘D‘)
dijkstrapath=DijkstraPath(node_map)
path=dijkstrapath(from_node, to_node)print path
运行结果：
原文：http://www.cnblogs.com/zxlovenet/p/4364385.html

转载自http://www.cnblogs.com/AndyJee/p/4640508.html 
题目： 

给定如下图所示的无向连通图，假定图中所有边的权值都为1； 

显然，从源点A到终点T的最短路径有多条，求不同的最短路径的数目。 

注：两条路径中有任意结点不同或者结点顺序不同，都称为不同的路径。



思路： 

给定的图中，边权相等且非负，Dijkstra最短路径算法退化为BFS广度优先搜索。实现过程中可以使用队列。 

计算到某结点最短路径条数，只需计算与该结点相邻的结点的最短路径值和最短路径条数，把最短路径值最小且相等的最短路径条数加起来即可。

答案：12

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

const int N=16;

int calNumOfPath(int G[N][N]){
    int stepNum[N]; // how many steps to reach i
    int pathNum[N]; // how many paths can reach i
    bool visited[N];
    memset(stepNum,0,N*sizeof(int));
    memset(pathNum,0,N*sizeof(int));
    memset(visited,false,N*sizeof(bool));
    stepNum[0]=0;
    pathNum[0]=1;

    queue<int> q;
    q.push(0);

    while(!q.empty()){
        int node=q.front();
        q.pop();
        visited[node]=true;
        int s=stepNum[node]+1;
        for(int i=0;i<N;i++){
            if(i!=node && !visited[i] && G[node][i]==1){
                if(stepNum[i]==0 || pathNum[i]>s){
                    stepNum[i]=s;
                    pathNum[i]=pathNum[node];
                    q.push(i);
                }
                else if(stepNum[i]==s){
                    pathNum[i]=pathNum[i]+pathNum[node];
                }
            }
        }
    }
    return pathNum[N-1];
}

int main()
{
    int G[16][16]={
    {0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
    {1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0},
    {0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0},
    {0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0},
    {1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
    {0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0},
    {0,0,1,0,0,1,0,1,0,0,1,0,0,0,0,0},
    {0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0},
    {0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0},
    {0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0},
    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
    {0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0},
    {0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0},
    {0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1},
    {0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0}};
    cout << calNumOfPath(G) << endl;
    return 0;
}

一心想学习算法，很少去真正静下心来去研究，前几天趁着周末去了解了最短路径的资料，用python写了一个最短路径算法。算法是基于带权无向图去寻找两个点之间的最短路径，数据存储用邻接矩阵记录。首先画出一幅无向图如下，标出各个节点之间的权值。
其中对应索引：
A ——> 0
B ——> 1
C ——> 2
D ——>3
E ——> 4
F ——> 5
G ——> 6
邻接矩阵表示无向图：
算法思想是通过Dijkstra算法结合自身想法实现的。大致思路是：从起始点开始，搜索周围的路径，记录每个点到起始点的权值存到已标记权值节点字典A，将起始点存入已遍历列表B，然后再遍历已标记权值节点字典A，搜索节点周围的路径，如果周围节点存在于表B，比较累加权值，新权值小于已有权值则更新权值和来源节点，否则什么都不做；如果不存在与表B，则添加节点和权值和来源节点到表A，直到搜索到终点则结束。
这时最短路径存在于表A中，得到终点的权值和来源路径，向上递推到起始点，即可得到最短路径，下面是代码：
#-*-coding:utf-8 -*-
classDijkstraExtendPath():def __init__(self, node_map):
self.node_map=node_map
self.node_length=len(node_map)
self.used_node_list=[]
self.collected_node_dict={}def __call__(self, from_node, to_node):
self.from_node=from_node
self.to_node=to_node
self._init_dijkstra()returnself._format_path()def_init_dijkstra(self):
self.used_node_list.append(self.from_node)
self.collected_node_dict[self.from_node]= [0, -1]for index1, node1 inenumerate(self.node_map[self.from_node]):ifnode1:
self.collected_node_dict[index1]=[node1, self.from_node]
self._foreach_dijkstra()def_foreach_dijkstra(self):if len(self.used_node_list) == self.node_length - 1:return
for key, val in self.collected_node_dict.items():  #遍历已有权值节点
if key not in self.used_node_list and key !=to_node:
self.used_node_list.append(key)else:continue
for index1, node1 in enumerate(self.node_map[key]):  #对节点进行遍历
#如果节点在权值节点中并且权值大于新权值
if node1 and index1 in self.collected_node_dict and self.collected_node_dict[index1][0] > node1 +val[0]:
self.collected_node_dict[index1][0]= node1 + val[0] #更新权值
self.collected_node_dict[index1][1] =keyelif node1 and index1 not inself.collected_node_dict:
self.collected_node_dict[index1]= [node1 +val[0], key]
self._foreach_dijkstra()def_format_path(self):
node_list=[]
temp_node=self.to_node
node_list.append((temp_node, self.collected_node_dict[temp_node][0]))while self.collected_node_dict[temp_node][1] != -1:
temp_node= self.collected_node_dict[temp_node][1]
node_list.append((temp_node, self.collected_node_dict[temp_node][0]))
node_list.reverse()returnnode_listdefset_node_map(node_map, node, node_list):for x, y, val innode_list:
node_map[node.index(x)][node.index(y)]= node_map[node.index(y)][node.index(x)] =valif __name__ == "__main__":
node= ['A', 'B', 'C', 'D', 'E', 'F', 'G']
node_list= [('A', 'F', 9), ('A', 'B', 10), ('A', 'G', 15), ('B', 'F', 2),
('G', 'F', 3), ('G', 'E', 12), ('G', 'C', 10), ('C', 'E', 1),
('E', 'D', 7)]
node_map= [[0 for val in xrange(len(node))] for val inxrange(len(node))]
set_node_map(node_map, node, node_list)#A -->; D
from_node = node.index('A')
to_node= node.index('D')
dijkstrapath=DijkstraPath(node_map)
path=dijkstrapath(from_node, to_node)print path
运行结果：