header

Shortestpath : Calculating the shortest path.
Tag:
Edit edit   Starstar

Program Information

Name: Shortestpath
Domain: Algorithm
Functionality: Calculating the shortest path.
Input:
     G:An undirected graph(Type: Graph) $v_{1}$:A vertex of G(Type: Vertex) $v_{2}$:A vertex of G(Type: Vertex)
Output:
     $ShortestPath(G,v_{1},v_{2}).length$

Reference

          A Formal Model for Metamorphic Relation Decomposition http://dx.doi.org/10.1109/WCSE.2013.14 Metamorphic Testing: Applications and Integration with Other Methods http://dx.doi.org/10.1109/QSIC.2012.21

MR Information


MR1


    Source input: $G_s,v^s_{1},v^s_{2}$ ; Source output: $ShortestPath(G_s,v^s_{1},v^s_{2}).length$
    Follow-up input: $G_f,v^f_{1},v^f_{2}$ ; Follow-up output: $ShortestPath(G_f,v^f_{1},v^f_{2}).length$
    Input relation: $G_f=G_s$ $v^f_{1}=v^s_{2}$ $v^f_{2}=v^s_{1}$
    Output relation: $ShortestPath(G_s,v^s_{1},v^s_{2}).length=ShortestPath(G_f,v^f_{1},v^f_{2}).length$

MR2


    Source input: $G_s,v^s_{1},v^s_{2}$ ; Source output: $ShortestPath(G_s,v^s_{1},v^s_{2}).length$
    Follow-up input: $G_f,v^f_{1},v^f_{2},v^f_{3}$ ; Follow-up output: $ShortestPath(G_f,v^f_{1},v^f_{3}).length,ShortestPath(G_f,v^f_{3},v^f_{2}).length$
    Input relation: $G_f=G_s$ $v^f_{1}=v^s_{1}$ $v^f_{2}=v^s_{2}$ $v^f_{3}$ is any vertex that appears in $ShortestPath(G_s,v^s_{1},v^s_{2})$
    Output relation: $ShortestPath(G_s,v^s_{1},v^s_{2}).length=ShortestPath(G_f,v^f_{1},v^f_{3}).length+ShortestPath(G_f,v^f_{3},v^f_{2}).length$

Related

Insert title here